[백준] 자바 16956 늑대와 양

문제

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

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

입력

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

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

출력

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

---

테스트 케이스

 

입력 1

5 5
.S...
...S.
S....
...S.
.S...

출력 1

1
.S...
...S.
S....
...S.
.S...

 

입력 2

1 2

SW

출력 2

0

 

입력 3

5 5
.S...
...S.
S....
...S.
.S...

출력 3

1
.S...
...S.
S....
...S.
.S...

---

접근

사이트의 예제 입력 3 예제 출력 3을 보고 많이 헷갈렸습니다.

중요한 것은 울타리(D)의 위치는 의미가 없었습니다. 그냥 늑대가 양에게 접근하지만 못하게 한다면 D는 어디에든 있어도 괜찮은 문제였습니다.

그래서 늑대의 위치 주변에 울타리만 BFS방식으로 설치해주니 문제가 해결되었습니다.

(늑대 위치 바로 옆에 양이 있다면 실패로 종료: 0 출력)

---

코드

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

class Node{
	int x;
	int y;
	public Node(int x,int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
    private static int r,c;
    private static char[][] graph;

    private static int[] dx = {0,0,1,-1};
    private static int[] dy = {1,-1,0,0};
    private static boolean flag;
    private static int result = 1;
    static void bfs() {
    	Queue<Node> q = new LinkedList<>();
    	for(int i=0; i<r; i++) {
    		for(int j=0; j<c; j++) {
    			if(graph[i][j] == 'W') {
    				q.add(new Node(i,j));
    			}
    		}
    	}
    	while(!q.isEmpty()) {
    		Node node = q.poll();
    		int nodex = node.x;
    		int nodey = node.y;
    		
    		for(int i=0; i<4; i++) {
    			int nx = nodex + dx[i];
    			int ny = nodey + dy[i];
    			
    			if(nx>=0 && nx<r && ny>=0 && ny<c) {
    				if(graph[nx][ny] =='S') {
    					result = 0;
    					return;
    				}
    				else if(graph[nx][ny] =='.') {
    					graph[nx][ny] = 'D';
    					
    				}
    			}
    		}
    	}
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        graph = new char[r][c];
        

        for(int i=0;i<r;i++) {
            String str = br.readLine();
            for(int j=0;j<c;j++) {
                graph[i][j] = str.charAt(j);
            }
        }
        bfs();
        bw.write(String.valueOf(result)+"\n");
        if(result == 1) {
        for(int i=0; i<r; i++) {
        	for(int j=0; j<c; j++) {
        		bw.write(graph[i][j]);
        	}
        	bw.write("\n");
        }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

---

주의

의미 없는 곳에 D가 있더라도 괜찮다.