문제
명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다.
해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 산화하려는 것으로 보인다. 이런 완벽에 가까운 물품인 모래를 두고서 해수욕이나 헤엄을 치는 것은 인생을 낭비하는 것과 같다고 생각한다. 하지만 아무도 명우의 말에 공감해주지 못했고, 결국 명우는 혼자서 모래성을 만들었다.
다른 친구들이 혼신의 힘을 다해 놀고있을 때 명우는 혼신의 힘을 다해 모래성을 쌓았다. 이 모래성은 언젠간 파도에 의해서 무너질 터... 명우는 이런 무너짐도 예술의 일환으로 이해한 사람이므로 무너지는 것도 고려해서 모래성을 만들었다.
그가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.
이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명이 궁금해졌다. 모래성은 위에 서술한 바와 같이 파도가 한번 칠 때마다 특정 부분이 무너저내리는 방식으로 모양이 변화된다. 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.
입력
첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000)
그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다.
각 문자는 1~9 사이의 숫자, 또는 '.' 이다. 1~9는 그 격자의 모래의 강도를 나타내며, '.'는 모래가 없다는 뜻이다.
모래성은 격자의 가장자리와 접해 있지 않다.
출력
몇번의 파도가 몰려오고나서야 모래성의 상태가 수렴하는지를 구한다.
해결 방법
우선 격자의 크기가 최대 1000 * 1000 = 1,000,000 이 될 수 있기 때문에, 파도가 칠 때마다 모든 맵을 검사하고 모래성의 상태를 검사하는 방법은 무조건 시간초과로 이루어진다.
이 문제에서 중요한 건 바로 모래성의 한 부분이 없어지면, 그 주변(대각선, 상하좌우) 모래성들의 강도가 1씩 낮아진다는 점이다.
예시를 보고 설명 해보겠다.
......
.939..
.3428.
.9393.
......위 예시에서 첫 번째 파도에 의해 강도가 3인 모래성이 전부 무너진다. 그러면 무너진 모래성 주변의 모래성들은 받는 면적이 한 칸씩 늘어나는 것이다.
이 점을 유의하면서 다음과 같은 풀이 방법을 생각해냈다.
- 맨 처음 주변을 비교해 빈 칸이 있을 때마다 강도를 1씩 낮춰가며, 강도가 음수가 되는 (첫 파도에 의해 부서질 예정) 모래성들을 전부 Queue 에다 담는다.
- 큐에서 좌표를 하나씩 꺼내며, 주변 모래성들의 강도를 1씩 낮춘다.
- 강도가 0이 되버리는 모래성은 파도에 의해 부서졌으므로, 그 주변 모래성들의 강도도 낮아져야 한다. 따라서 Queue에다 추가한다.
- Queue가 빌 때 까지 반복한다.
......
.939..
.3428.
.9393.
......
위 예시에서 주변 빈칸에 따라 강도를 낮추면 격자는 다음과 같은 상태가 된다.
......
.405..
.0414.
.406(-2).
......여기서 강도가 음수가 되버리는 모래성들을 전부 Queue에다 집어넣고, BFS 를 통해 Queue 가 빌 때가지 반복한다. Queue 가 빌 때의 반복 횟수가 바로 정답이 된다.
public class P10711 {
static int[][] map;
static final int EMPTY = -100000000;
static final int[][] dxDy = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(in));
StringBuilder sb = new StringBuilder();
StringTokenizer mapInfo = new StringTokenizer(br.readLine());
int N = Integer.parseInt(mapInfo.nextToken());
int M = Integer.parseInt(mapInfo.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
if (input.charAt(j) == '.') {
map[i][j] = EMPTY;
} else {
map[i][j] = input.charAt(j) - '0';
}
}
}
System.out.println(solution(N, M));
}
static int solution(int N, int M) {
return bfs(initEmptyCount(N, M));
}
static int bfs(Queue<Point> points) {
int count = 0;
while (!points.isEmpty()) {
//Queue에 들어가 있는 좌표가 모두 이번 턴에 무너지는 모래성이므로, 사이즈만큼 반복 진행
int size = points.size();
while (size-- > 0) {
Point temp = points.poll();
//무너진 모래성 좌표 주변의 강도를 전부 1씩 낮춰줌
for (int[] move : dxDy) {
int X = temp.x + move[0];
int Y = temp.y + move[1];
map[Y][X]--;
//만약 강도가 0이 되버리는 모래성이 있으면, 무너질 예정이므로 큐에 추가한다.
if (map[Y][X] == 0) {
points.add(new Point(X, Y));
}
}
}
count++;
}
return count;
}
//첫 파도에 의해 무너질 모래성들을 전부 Queue 에다 집어넣는다.
static Queue<Point> initEmptyCount(int N, int M) {
Queue<Point> points = new LinkedList<>();
for (int i = 1; i < N - 1; i++) {
for (int j = 1; j < M - 1; j++) {
//만약 현재 좌표가 모래성이면, 주변 빈 칸을 비교해 강도를 낮춘다.
if (map[i][j] > 0) {
for (int[] move : dxDy) {
int X = j + move[0];
int Y = i + move[1];
if (map[Y][X] == EMPTY) {
map[i][j]--;
}
}
//만약 강도가 0 이하가 되면 부서진다는 뜻이므로 큐에 추가한다.
if (map[i][j] <= 0) {
points.add(new Point(j, i));
}
}
}
}
return points;
}
}
Comment