[백준] 16956. 늑대와 양 (실버3) - BFS

16956. 늑대와 양 (실버3)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	7316	3540	2634	47.847%

문제

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

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

입력

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

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

출력

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

예제 입력 1
6 6
..S...
..S.W.
.S....
..W...
...W..
......

예제 출력 1
1
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

예제 입력 2
1 2
SW

예제 출력 2
0

풀이

1. 배열 돌면서 늑대(w)나오면 사방검사를 한다
2. 사방검사 해서 양(s)이 나오면 불가(0), 양이 아니면 울타리(D)를 친다.

public class Search_16956 {
	public static int R,C;
	public static String[][] arr; //위치 배열
    // 사방검사
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 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());

		arr = new String[R][C];
		
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			String[] strArr = str.split("");
			for(int j = 0; j < C; j++) {
				arr[i][j] = strArr[j];
			}
		}
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(arr[i][j].equals("W")) {
					for(int t =0;t<4; t++) {
						int xx = i + dx[t];
						int yy = j + dy[t];
						if(xx<0 || xx>R-1 || yy<0 || yy>C-1 ) continue;
                        //양이 나오면 진행 불가
						if(arr[xx][yy].equals("S")) {
							System.out.println("0");
							System.exit(0);
                            
                         // 양아 아닌 빈칸이 나오면 울타리를 친다.
						}else if(arr[xx][yy].equals(".")) {
							arr[xx][yy]="D";
						}
					}
				}
			}
		}
		
        // 양이 잡아 먹히지 않으면 성공(1) 찍고 배열 출력
		System.out.println("1");
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}

	}
}

* BFS 사용