[백준] 아기돼지와 늑대 (Java)

문제

---

산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.

고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.

고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.

게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 '안전한 곳'이라고 부릅니다. 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

입력

---

첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다.

i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 '.' 일 경우 초원, '+' 일 경우 빙판, '#' 일 경우 산, 그리고 'W'는 늑대가 살고 있음을 나타냅니다. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

출력

---

입력으로 주어진 지도를 출력하되 아기돼지가 살 수 있는 초원은 문자 'P'로 대체하여 출력합니다.

SOL

---

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

//https://www.acmicpc.net/problem/16441
public class Main {
    static int N, M;
    static char[][] map;
    static boolean[][] visited;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Initialize
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];

        int[][] wolf = new int[N * M][2];
        int wCnt = 0;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                if (line.charAt(j) == '.') map[i][j] = 'P';  // 우선 초원의 위치를 P으로 표시
                else {
                    if (line.charAt(j) == 'W') wolf[wCnt++] = new int[]{i, j};
                    map[i][j] = line.charAt(j);
                }
            }
        }

        for (int i = 0; i < wCnt; i++) {
            // wolf
            Queue<int[]> q = new LinkedList<>();
            q.add(wolf[i]);

            while (!q.isEmpty()) {
                int[] curr = q.poll();
                for (int j = 0; j < 4; j++) {
                    int currY = curr[0] + dy[j];
                    int currX = curr[1] + dx[j];
                    if (isValid(currY, currX) && !visited[currY][currX]) {
                        char c = map[currY][currX];
                        if (c != '#') {
                            // 아직 지나지 않은 초원이라면
                            if (c == 'P') map[currY][currX] = '.';
                                // 빙판길을 건넌 것이라면
                            else if (c == '+') { //
                                // 현재 길이 빙판길이면서 다음 위치가 산이 아니거나 이동할 수 있는 거리면 이동
                                while (isValid(currY + dy[j], currX + dx[j])
                                        && map[currY][currX] == '+'
                                        && map[currY + dy[j]][currX + dx[j]] != '#') {
                                    currY += dy[j];
                                    currX += dx[j];
                                }
                                // 현재 위치가 안전한 초원이라면
                                if (map[currY][currX] == 'P') map[currY][currX] = '.';
                            }

                            // 늑대가 방문하지 않았던 곳이라면 방문체크/큐에 추가
                            if (!visited[currY][currX]) {
                                visited[currY][currX] = true;
                                q.add(new int[]{currY, currX});
                            }
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) sb.append(map[i][j]);
            sb.append("\n");
        }
        System.out.println(sb);

        br.close();
    }

    static boolean isValid(int y, int x) {
        return y >= 1 && y < N - 1 && x >= 1 && x < M - 1;
    }
}