백준 C++ 알고리즘 2573: 빙산

 

 

 

BFS로 풀어야 하는 문제이다.

 

문제 자체 난이도는 쉽게 느껴진다.

 

기본적인 로직은,  빙산을 조건에 맞게 줄이고 덩어리의 개수를 세는 것이며 이를 조건에 맞을 때 까지 반복하는 것이다.

 

 

1. 가장 상위 반복문을 while(1)로 구현했다. 종료 조건은 반복문 내의 BFS가 작동하지 않거나, 덩어리의 개수가 2개 이상이 된 시점이다.

 

2. 유의해야 할 부분은, BFS 구현 보다는 빙산의 높이가 줄어드는 과정에서 이차원 배열의 값을 어떻게 처리할지인 것 같다.

 

3. 임시 벡터를 구현하여 값을 비교하고, 값을 처리하는건 본체 배열에서 행하도록 하여 구현하였는데, 이보다 좋은 구현 방법이 있을 것 같긴 하다.

 

4. 또한 방문 확인 노드를 잘 처리해야 한다.

 

5. 벡터의 assign 함수와 resize 함수를 적절히 사용해야 한다.

 

#include <iostream>
#include <queue>
#include <vector>

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;

	std::vector<std::vector<int>> list(n, std::vector<int>(m, 0));
	for (int i{ 0 }; i < n; i++) {
		for (int j{ 0 }; j < m; j++) {
			std::cin >> list[i][j];
		}
	}
	int y[] = { 1, 0, -1, 0 };
	int x[] = { 0, -1, 0, 1 };

	int cnt = 0;
	int ans = 0;
	std::queue<std::pair<int, int>> q;
	std::vector<std::vector<bool>> v;

	while (1) {
		std::vector<std::vector<int>> tmp = list;
		for (int i{ 0 }; i < n; i++) {
			for (int j{ 0 }; j < m; j++) {
				cnt = 0;
				for (int k{ 0 }; k < 4; k++) {
					if (tmp[i][j] > 0 && i + y[k] >= 0 && i + y[k] < n && j + x[k] >= 0 && j + x[k] < m) {
						if (tmp[i + y[k]][j + x[k]] <= 0) cnt++;
					}
				}
				list[i][j] -= cnt;
			}
		}

		v.assign(n, std::vector<bool>(m,false));

		cnt = 0;
		for (int i{ 0 }; i < n; i++) {
			for (int j{ 0 }; j < m; j++) {
				if (list[i][j] > 0 && v[i][j] == false) {
					q.push({ i,j });
					while(!q.empty()) {
						int a = q.front().first;
						int b = q.front().second;
						q.pop();

						for (int k{ 0 }; k < 4; k++) {
							if (a + y[k] >= 0 && a + y[k] < n && b + x[k] < m && b + x[k] >= 0 && list[a+y[k]][b+x[k]] > 0 && !v[a+y[k]][b+x[k]]) {
								q.push({ a + y[k], b + x[k] });
								v[a + y[k]][b + x[k]] = true;
							}
						}
					}
					cnt++;
				}
			}
		}
		ans++;
		if (cnt >= 2) {
			break;
		}
		if (cnt == 0) {
			ans = 0;
			break;
		}
	}

	std::cout << ans << "\n";
}