[백준] BOJ 10711 모래성 (골드 2)

문제

---

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

10711: 모래성

 

---

해설

---

1. 2개의 2차원 배열을 사용한다.
   
   • 맵 배열 .은 0으로 나머지 수는 그대로 사용하여 맵을 만들어낸다.
   • 나머지는 해당 맵의 x,y에 몇개의 파도 (0)이 존재하는지를 저장한다.
2. 모든 파도(0)에 대하여 BFS를 수행한다.
   • 이는 현재 파도인 경우만 탐색한다. (이번 탐색의 파도에 의해 무너진 모래성을 0으로 보면 안된다.)
   • 만약, 탐색 도중 파도에 의해 무너진 모래성의 일부가 있다면 이를 다음 탐색의 nextQueue에 넣어둔다.
3. 모든 파도에 대해 수행하면 ++count[nx][ny]를 통해 해당 위치에 8방향에 파도가 몇개 있는지가 갱신된다.
4. 이때, 새롭게 모래성 -> 파도로 변한 것만을 nextQueue에 넣었고,
   (모든 파도에 대해서 다시 탐색 X, 새롭게 파도가 된 것만 확인)
   count[][]는 초기화되지 않았으므로 다시 전체를 탐색하지 않아도 된다. (시간 최적화 포인트)
5. 이렇게 수행하다보면 모래성이 더 이상 파도로 변하지 않는 순간이 온다. (이는, nextQueue에 원소가 하나도 없는 것)
   
   
6. 이때의 time을 출력한다.

---

코드 (BFS, 시뮬레이션)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ10711 {
    static int[][] map;
    static int[][] count;
    static Queue<Pair> queue = new ArrayDeque<Pair>();
    static int N, M;

    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        count = new int[N][M];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = input.charAt(j);
                if (c == '.') {
                    map[i][j] = 0;
                    queue.offer(new Pair(i, j));
                } else {
                    map[i][j] = c - '0';
                }
            }
        }
        int time = 0;
        while (true) {
            if(simulation()) break;
            time++;
        }
        System.out.println(time);
    }

    private static boolean simulation() {
        Queue<Pair> nextQueue = new ArrayDeque<>();
        while (!queue.isEmpty()) {
            Pair p = queue.poll();

            for (int i = 0; i < 8; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 0) continue;
                if (++count[nx][ny] == map[nx][ny]) {
                    map[nx][ny] = 0;
                    nextQueue.offer(new Pair(nx, ny));
                }
            }
        }

        if(nextQueue.isEmpty()) return true;
        queue = nextQueue;
        return false;
    }
}

class Pair{
    int x, y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

---

결론

---

치즈와 마찬가지로 모래성이 아닌 바깥부터 탐색을 시작하고, 

변경된 부분만을 다시 큐에 넣어서 탐색하는 것이 시간 효율성을 높이는 것이 포인트이다.

---