백준 16956

늑대와 양 

문제

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

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

---

입력

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

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

---

출력

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

---

풀이

스페셜 저지이므로 예제 출력과 답이 달라도 상관 없다.

늑대의 좌표에서 상하좌우만 검사해서 양을 찾으면 즉시 종료하고, 그외에는 울타리 설치를 한다.

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

public class Main16956 {
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	//상하좌우 

	static int R;
	static int C;
	
	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()); //R x C 크기의 목장 
		
		char[][] map = new char[501][501];
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(map[i][j] == 'S') { //만약 늑대이면 
					//상하좌우에 양이 있는지 검사
					for(int k=0; k<4; k++) {
						int ny = i + dy[k];
						int nx = j + dx[k];
						
						if(!valid(nx, ny)) continue;
						
						if(map[ny][nx] == 'W') { //늑대와 양이 인접하면 울타리 설치 불가 
							System.out.println(0);
							System.exit(0);
						}else if(map[ny][nx] == 'S' || map[ny][nx] == 'D') { //늑대 주변에 늑대,울타리면 스킵 
							continue;
						}else if(map[ny][nx] == '.') { //빈공간이면 울타리 설
							map[ny][nx] = 'D';
						}
						
					}//이 반복문이 종료되면 늑대 한마리의 검사가 끝난다.
				}
			}
		}
		
		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 valid(int x, int y) {
		if(x < 0 || y < 0 || x > C-1 || y > R-1) {
			return false;
		}
		return true;
	}
	
	
}