백준 2573번 빙산 C++ BFS, 완전 탐색, 시뮬레이션, 구현

리뷰

 

큐를 사용하여 적절한 조건문과 BFS를 조합하여 풀었다.

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

 

문제 풀이

1. 전역 변수로 n, m, ans = 0과 2차원 배열로 맵용 lst 및 섬 덩어리를 찾을 chk와 방향배열을 넣어주었다.
2. 좌표와 현재 값을 나타낼 Pos 구조체를 정의해 주고 Pos구조체 타입의 큐 q를 초기화 해주었다.
3. input함수를 통해 n, m값을 입력 받고, 맵의 정보를 받아온다. 이때 빙산은 q에 저장해 준다.
4. solution함수를 통해 시뮬레이션 및 전반적인 답을 도출해 낼 것이다.
5. 재귀를 통해 직관적으로 확인해도 되지만, 나는 그냥 while문을 통해 시간의 흐름을 나타냈다.
6. time을 0으로 초기화 하고 while문을 항상 true로 실행한다.
7. chk_island 함수를 통해 BFS로 섬이 몇덩어리로 나누어져 있는지 체크해 준다.
8. 섬의 개수를 flag = 0으로 초기화 해주고 방문 배열을 0으로 초기화 해준다.
9. 맵 lst를 탐색하며 0 이상이고 방문하지 않은 빙산을 만난다면 해당 좌표로부터 Union함수를 실행해 준다.
10. Union 함수에서는 BFS를 통해 연결된 섬을 모두 방문처리 해준다.
11. 만약 flag값이 2 이상이라면 2덩이 이상의 섬이 확인된 것이므로 바로 return 처리해 주면 된다.
12. chk_island의 결과가 2라면 ans를 time으로 최신화 해주고 solution을 종료한다.
13. 만약 결과가 0인 경우에는 빙산이 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는 경우이기에 return 해준다.
14. 결과가 1일 경우에는 아직 빙산이 한 덩어리이기 때문에 녹여주는 작업을 진행해 주면 된다.
15. q에 존재하는 빙산들을 순회하고 4방향을 탐색하여 주변에 0의 개수만큼 현재 빙산의 값을 빼준다.
16. 모든 빙산에 동일한 작업을 진행해 주고, 현재 빙산의 값이 0보다 작거나 같을 경우 맵에서 0으로 변경해 준다.
17. 빙산이 값이 1이상일 경우에는 q에 다시 push해주면 된다.
18. 작업이 완료된 후에는 time을 1 증가시켜 준다.
19. 이후 7번부터 동일한 작업을 쭉 진행해 주면 된다.

 

참고 사항

BFS를 탐색하며 빙산이 모두 녹는 경우라고 바로 맵상에서 0으로 바꿔준다면 다음 빙산을 탐색할때 원치 않는 결과를 초래할 수가 있다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
int n, m, ans = 0;
int lst[300][300];
int chk[300][300];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y, val;
};

queue<Pos> q;

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
			if (lst[i][j]) q.push({ i, j, lst[i][j] });
		}
	}
}

void Union(int x, int y) {
	queue<Pos> now;
	now.push({ x, y });
	chk[x][y] = 1;

	while (!now.empty()) {
		Pos pos = now.front(); now.pop();
		int cx = pos.x, cy = pos.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !chk[nx][ny] && lst[nx][ny]) {
				chk[nx][ny] = 1;
				now.push({ nx, ny });
			}
		}
	}
}

int chk_island() {
	int flag = 0;
	memset(chk, 0, sizeof(chk));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] && !chk[i][j]) {
				if (flag) return 2;
				flag++;
				Union(i, j);
			}
		}
	}
	return flag;
}

void solution() {
	int time = 0;
	while (1) {
		int result = chk_island();
		if (result == 2) {
			ans = time;
			return;
		}
		else if (!result) return;
		queue<Pos> temp;
		while (!q.empty()) {
			Pos pos = q.front(); q.pop();
			int cx = pos.x, cy = pos.y, cv = pos.val;
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i], ny = cy + dy[i];
				if (0 <= nx && nx < n && 0 <= ny && ny < m && !lst[nx][ny]) cv--;
			}
			temp.push({ cx, cy, cv });
		}
		while (!temp.empty()) {
			Pos pos = temp.front(); temp.pop();
			if (pos.val > 0) q.push(pos);
			else lst[pos.x][pos.y] = 0;
		}
		time++;
	}
}

int main() {
	input();
	solution();
	cout << ans;
}