2573. 빙산

이 문제는 완전탐색문제의 하나의 과정을 추가한 문제이다. 

문제 요약 )

1. 각 빙산의 값(matrix에 있는 숫자값)은 시간이 지남에 따라 4방(상/하/좌/우)에 0의 갯수만큼 녹는다. 
2. 시간이 지남에 따라 빙산이 녹을 때, 한 덩어리의 빙산이 2개 이상으로 나눠지는 순간을 찾아라.

문제요약 1은 완전탐색 BFS을 이용하여 쉽게 구현할 수 있다. 여기서 유의점은 순차 탐색을 하면서 (i,i)이 녹아 0이 되었을 때, 다음값인 (i,i+1)에서는 (i,i)값을 녹았다고 생각하면 안된다. 그 이유는 동시에 녹기 때문에 (i,i+1)값을 계산할 때 (i,i)값이 있다고 생각한다. 

문제요약 2의 경우,

1. 처음에 빙하의 총 갯수를 구해놓고, 빙하가 녹을 때마다 개수를 조정한다.
2. 그리고 하나의 시간 단위가 지났을 때, 아무 빙하로 DFS를 하여 연결된 빙하 갯수를 찾는다. 
3. 총 개수와 연결된 빙하 개수가 동일하다면, 아직 한덩어리이기 때문에 연산을 계속한다.
4. 아니라면 time을 출력하고 멈춘다.

 

여기서 주의점. 빙하가 다 녹을 때까지 2 덩어리로 나눠지지 않는다면 0을 출력해야된다. 이를 유의하자. 나는 이점을 코딩안해서 30분 동안 찾느라 고생했다... 

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include<algorithm>
using namespace std;

typedef struct iceberg {
	int i;
	int j;
};

queue<iceberg> list;
int iceberg_count = 0;
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
int c, r;
int i_c = 1;
void dfs(int i, int j, int map[][310]) {
	int box = map[i][j];
	map[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] < c && j + dy[k] >= 0 && j + dy[k] < r) {
			if (map[i + dx[k]][j + dy[k]] > 0) {
				i_c++;
				dfs(i + dx[k], j + dy[k],map);
			}
		}
	}
}

int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	int map[310][310];
	cin >> c >> r;
	for (int i = 0; i < c; i++) {
		for (int j = 0; j < r; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				iceberg_count++;
				list.push({ i,j });
			}
		}
	}
	list.push({ -1,-1 });
	int time = 0;
	vector<iceberg> li;
	while (list.size() > 0) {
		int count = 0;
		int i = list.front().i;
		int j = list.front().j;
		list.pop();
		if (i == -1 && j == -1) { // 하나의 시간 묶음이 끝났다면, 
			if (list.empty()) { //빙하가 다 녹았는데 두 덩어리로 안 나뉜 경우.
				cout << 0;
				return 0;
			}
			list.push({ -1,-1 });//시간의 경계선을 넣어준다.
			i_c = 1;
			int l[310][310] = { 0 };
			for (int i = 0; i < c; i++) {
				for (int j = 0; j < r; j++) {
					l[i][j] = map[i][j];
				}
			}//map 배열을 복사한다. dfs를 돌릴 경우, 함수안에서의 값 변경이 원형 데이터에 영향을 주기 때문에
			dfs(list.front().i, list.front().j,l);
			time++;
			if (i_c != iceberg_count) {
				cout << time;
				return 0;
			}
			while(li.size()) { // 0이 아니라 음수 처리해줬던 값들을 모두 0으로 다시 처리해준다. 
				iceberg n = li.back();
				li.pop_back();
				map[n.i][n.j] = 0;
			}
			i = list.front().i;
			j = list.front().j;
			list.pop();
		}
		for (int k = 0; k < 4; k++) { //사방에 0의 개수를 찾는다
			if (i + dx[k] >= 0 && i + dx[k] < c && j + dy[k] >= 0 && j + dy[k] < r) {
				if (map[i + dx[k]][j + dy[k]] == 0)
					count++;
			}
		}
		map[i][j] -= count;
		if (map[i][j] <= 0) { // 다 녹은 경우 음수로 만들고 li배열에 입력한다. 
			map[i][j] = -1;
			li.push_back({ i,j });
			iceberg_count--; // 전체 빙하개수도 수정한다. 
		}
		else {
			list.push({ i,j }); // 아직 빙하가 남아있다면, list에 다시 추가해준다
		}
		
	}




	return 0;
}

 

https://www.acmicpc.net/problem/2573

2573번: 빙산