[BaekJoon] 10711 모래성 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int H, W;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Loc> queue;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1};

    static void input() {
        Reader scanner = new Reader();

        H = scanner.nextInt();
        W = scanner.nextInt();
        map = new int[H][W];
        visited = new boolean[H][W];
        queue = new LinkedList<>();

        for(int row = 0; row < H; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < W; col++) {
                if(info.charAt(col) == '.') map[row][col] = 0;
                else map[row][col] = info.charAt(col) - '0';
            }
        }
    }

    static void solution() {
        init();
        System.out.println(bfs());
    }

    static int bfs() {
        int time = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();

            for(int count = 0; count < size; count++) {
                Loc cur = queue.poll();

                map[cur.x][cur.y] = 0;
                for(int dir = 0; dir < 8; dir++) {
                    int cx = cur.x + dx[dir], cy = cur.y + dy[dir];

                    if(isInMap(cx, cy)) {
                        if(!visited[cx][cy] && map[cx][cy] != 0) {
                            int emptyCount = getEmptyLocNum(cx, cy);
                            if(emptyCount >= map[cx][cy]) {
                                visited[cx][cy] = true;
                                queue.offer(new Loc(cx, cy));
                            }
                        }
                    }

                }
            }

            time++;
        }

        return time;
    }

    static void init() {
        for(int row = 0; row < H; row++) {
            for(int col = 0; col < W; col++) {
                if(map[row][col] == 0 || map[row][col] == 9) continue;

                int count = getEmptyLocNum(row, col);

                if(count >= map[row][col]) {
                    visited[row][col] = true;
                    queue.offer(new Loc(row, col));
                }
            }
        }
    }

    static int getEmptyLocNum(int x, int y) {
        int count = 0;

        for(int dir = 0; dir < 8; dir++) {
            int cx = x + dx[dir], cy = y + dy[dir];
            if(isInMap(cx, cy) && map[cx][cy] == 0) count++;
        }

        return count;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < H && y >= 0 && y < W) return true;
        return false;
    }

    static class Loc {
        int x, y;

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";

            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }

}

4.  접근

• 각 격자별로 주변 8방향에서 모래성이 쌓여있지 않은 부분의 개수를 구하고 그 개수가 튼튼함의 정도보다 크거나 같다면 Queue에 해당 격자들을 넣어 BFS를 통해 모래성의 상태가 수렴되는 시간을 구합니다.
• 우선 처음에 Queue를 하나 생성하고 각 격자들을 순회하며 주변에 모래성이 쌓여있지 않은 부분의 개수를 구하여 그 개수가 해당 격자의 튼튼함보다 크거나 같다면 해당 격자를 Queue에 담습니다.
  • 이 때, 해당 격자의 튼튼함이 0이면 이미 모래성이 없는 상태이므로 주변에 모래성이 쌓여있지 않은 부분의 개수를 구하지 않고, 튼튼함이 9라면 주변에 모두 모래성이 없더라도 절대 무너지는 일이 없기 때문에 해당 격자는 주변에 모래성이 쌓여있지 않은 부분의 개수를 구하지 않습니다.
• BFS를 통해 모래성의 상태가 수렴되는 시간을 구합니다.
  • 파도가 한 번 칠 때마다 상태가 변경되어야 하기 때문에 BFS 탐색을 시작하기 직전에 Queue에 있는 격자들에 대해서만 탐색을 진행하고 BFS 탐색을 하고 난 후에 파도가 친 횟수를 1 증가시킵니다.
  • BFS 탐색 후에 Queue가 비어있다면, 더이상 상태 변경이 일어나지 않았다는 뜻이므로 모래성의 상태가 수렴되었다는 뜻이 되기 때문에 그 때까지 파도 친 횟수가 답이 됩니다.