BOJ 16956 늑대와 양

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

문제

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

---

입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. ‘.’는 빈 칸, ‘S’는 양, ‘W’는 늑대이다.

---

출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 ‘D’로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

---

제한

1 ≤ R, C ≤ 500

---

예제 입력 1

6 6
..S...
..S.W.
.S....
..W...
...W..
......

예제 출력 1

1
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

예제 입력 2

1 2
SW

예제 출력 2

0

… 이하 예제 생략

---

코드

맨 처음 문제를 접했을 때, 양을 기준으로 울타리를 세워야 한다고 생각하니 상당히 어렵게 느껴졌었다.

하지만 늑대를 기준으로 이동할 수 있는 곳을 체크하면서 양과 접촉하는 지점에 울타리를 만들면 그렇게 어렵지 않은 문제였다.

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dirRow = {1, -1, 0, 0}, dirCol = {0, 0, 1, -1};
    static boolean isImpossible = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = (char) br.read();
            }
            br.read();
        } // 문제에 주어진 양과 늑대의 위치로 지도를 만든다

        // 지도의 각 인덱스를 방문하며 늑대가 있을 때마다 DFS로 해당 늑대가 이동할 수 있는 지역을 탐색한다.
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == 'W') { // 맨 처음 주어진 늑대의 위치가 양과 바로 붙어있다면, 불가능한 경우이므로 검사를 종료한다.
                    for (int k = 0; k < dirRow.length; k++) {
                        int newRow = i + dirRow[k], newCol = j + dirCol[k];
                        boolean isInside = newRow >= 0 && newRow < R && newCol >= 0 && newCol < C;
                        if(isInside && map[newRow][newCol] == 'S') {
                            isImpossible = true;
                            break;
                        }
                    }
                    DFS(i, j); // 양과 바로 붙어있지 않았다면, 검사를 실시한다.
                    map[i][j] = 'W'; // DFS의 탐색으로 인해, 지도에서 맨 처음 늑대의 위치가 'O'로 변한 것을 'W'로 되돌린다.
                }
            }
            if(isImpossible) break;
        }

        // 정답 출력
        StringBuilder answer = new StringBuilder();
        answer.append(isImpossible ? 0 : 1).append('\n');
        if(!isImpossible) {
            for (char[] row: map) {
                for (char col: row) {
                    answer.append(col == 'O' ? '.' : col);
                }
                answer.append('\n');
            }
        }

        System.out.println(answer);
    }

    static void DFS(int row, int col) {
        // 방문한 곳의 주변에 양이 있다면, 방문한 곳을 울타리로 설정
        for (int i = 0; i < dirRow.length; i++) {
            int newRow = row + dirRow[i], newCol = col + dirCol[i];
            boolean isInside = newRow >= 0 && newRow < R && newCol >= 0 && newCol < C;
            if(isInside && map[newRow][newCol] == 'S') {
                map[row][col] = 'D';
                return;
            }
        }
        map[row][col] = 'O'; // 주변에 양이 없으면, 방문 처리

        for (int i = 0; i < dirRow.length; i++) { // 주변에 아직 방문하지 않은 곳이 있으면 DFS로 방문
            int newRow = row + dirRow[i], newCol = col + dirCol[i];
            boolean isInside = newRow >= 0 && newRow < R && newCol >= 0 && newCol < C;
            if(isInside && map[newRow][newCol] == '.') DFS(newRow, newCol);
        }
    }
}