백준 10711: 모래성

문제 요약

그가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.

이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

문제의 입력을 모두 받고, 어떤 ary[i][j]가 첫 파도에 무너질 경우라면 {i, j}를 큐에 삽입한다. {i, j}가 무너지는 경우는 해당 포인트를 중심으로 8방향의 0의 개수가 ary[i][j]보다 많으면 된다. i, j의 위치가 다음번에 무너지는 지 여부를 isCollapse(int i, int k)로 정의하였다.
한 번의 파도가 지나 모래성이 무너졌다면, 그 다음에 무너질 포인트는 그 주변 8방향의 지점 뿐이다. 이에 무너진 지점을 중심으로 8방향 모두 isCollapse()를 통해 무너질 예정인지 검사하고, 그렇다면 큐에 삽입한다. 큐에 삽입되는 포인트가 없어질 때까지 반복하여, level을 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, m, ary[1000][1000];
int dir[8][2] = { {0,1} , {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1} };
bool visited[1000][1000];

bool isCollapse(int i, int j)
{
	int cnt = 0;
	for (int k = 0; k < 8; k++) {
		int ik = i + dir[k][0];
		int jk = j + dir[k][1];
		if (ik >= 0 && ik < n && jk >= 0 && jk < m) {
			if (!ary[ik][jk]) cnt++;
		}
	}
	if (cnt >= ary[i][j]) return true;
	return false;
}

int main()
{
	queue<pair<int, int >> q;
	int qsize, level = 0;
	scanf("%d%d", &n, &m);
	char in;
	getchar();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%c", &in);
			if (in == '.') ary[i][j] = 0;
			else ary[i][j] = in - '0';
		}
		getchar();
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (ary[i][j] && isCollapse(i, j)) {
				q.push({ i, j });
				visited[i][j] = true;
			}
		}
	}
	while (!q.empty()) {
		qsize = q.size();
		level++;
		while (qsize--) {
			auto t = q.front();
			ary[t.first][t.second] = 0;
			for (int k = 0; k < 8; k++) {
				int ik = t.first + dir[k][0];
				int jk = t.second + dir[k][1];
				if (ary[ik][jk] && isCollapse(ik, jk) && !visited[ik][jk]) {
					visited[ik][jk] = true;
					q.push({ ik, jk });
				}
			}
			q.pop();
		}
	}
	cout << level;

}