[백준] 16956번 늑대와 양 - Java, 자바

난이도

실버 3

문제

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

풀이

문제를 읽고 그래프 탐색으로 풀면 된다고 생각했는데, 예제 출력이 내가 생각했던 거랑 달라서 다른 방식으로 풀어야하나 고민했다.
알고 보니 이 문제는 "스페셜저지" 문제로 답안이 여러 개가 될 수 있는 문제 ,,, (몰랐다)
원래 생각하던 방식으로 다시 문제를 풀었다!

1. 늑대의 위치를 저장한다.
2. bfs 방식과 비슷하게 탐색을 진행한다.
   큐에서 값을 하나 빼기
   상하좌우로 움직일 수 있는지 판단하기
   '.'=빈칸이 있는 경우 울타리를 설치
   'S'=양이 있는 경우 flag 값을 false로 바꾸고 return
3. flag 값을 따라 출력을 달리 한다.

코드

package 백트래킹;

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

public class BOJ16956 {
    static int r, c;
    static char[][] map;
    static Queue<int[]> q = new LinkedList<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean flag = true;

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


        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 s = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'W') {
                    q.add(new int[]{i, j});
                }
            }
        }
        bfs();

        if (flag) {
            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();
            }
        } else {
            System.out.println("0");
        }


    }

    static void bfs() {
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int x = t[0];
            int y = t[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                    if (map[nx][ny] == '.') {
                        map[nx][ny] = 'D';
                    }
                    if (map[nx][ny] == 'S') {
                        flag = false;
                        return;
                    }
                }
            }
        }
    }
}