[백준 | Java] 16956 늑대와 양

내 풀이

울타리의 최소 갯수를 구하는 문제가 아니므로, 늑대의 상하좌우 칸을 탐색해 울타리를 친다.
알고리즘 유형은 굳이 나누자면 BFS?같다
출발지로부터 인접한 한 칸까지만 탐색하지만,,

만일, 늑대와 양이 붙어있다면 어떻게 해도 늑대와 양은 만나기 때문에 바로 0을 출력하고, 그게 아니라면 해당 칸에는 울타리를 친다.
이 때, 늑대와 늑대도 붙어있을 수 있으므로 탐색하는 칸에도 늑대가 있다면 울타리를 치지 않고 넘어가서 다음을 탐색한다.

쉬운 문제였지만 늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하라는 요구사항을 못 보고 구현해서 틀렸다.
요구사항을 꼼꼼하게 보고 풀어야겠다,,,,

답이 여러개일 수 있는 스페셜 저지 문제이다.
내 코드로 예제 1번 실행 시 출력은 다음과 같이 나온다.

1
..S.D.
..SDWD
.SD.D.
.DWD..
..DWD.
...D..

코드

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;

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

    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++) {
            String tmp = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = tmp.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'W') {
                    if (setFence(i, j)) {
                        System.out.println(0);
                        return;
                    }
                }
            }
        }

        System.out.println(1);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static boolean setFence(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
                if (map[nx][ny] == 'S')  // 늑대 주변에 양이 붙어있는지 확인
                    return true;
                else if (map[nx][ny] == 'W')  // 늑대 주변에 늑대가 붙어있는지 확인
                    continue;
                else
                    map[nx][ny] = 'D';
            }
        }
        return false;
    }
}