[백준_16956번] 늑대와 양

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

16956번: 늑대와 양

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

/*
 * 해당 문제는 설치할 울타리의 최소 갯수를 구하는 것이 아니기 때문에
 * 울타리의 개수 상관없이 늑대가 양이 있는 칸에 못가게 만들면 된다.
 * 즉, 늑대의 상,하,좌,우 칸에 양이 없으면 늑대는 양에 갈 수 없기 때문에 해당 칸들에 울타리를 설치하면 된다.
 */
public class BaekJoon_16956 {
	static char[][] map;
	static int r,c;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		map=new char[r][c];
		
		for(int i=0;i<r;i++) {
			String str=sc.next();
			for(int j=0;j<c;j++) {
				map[i][j]=str.charAt(j);
			}
		}
		
		boolean flag=true; 
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				
				// 해당 칸에 늑대가 있다면 상,하,좌,우 탐색
				if(map[i][j]=='W') {
					for(int k=0;k<4;k++) {
						int nx=i+dx[k];
						int ny=j+dy[k];
						
						// 배열 범위를 벗어난 경우 넘어간다.
						if(nx>=r||ny>=c||nx<0||ny<0)
							continue;
						
						/*
						 * 늑대가 이동할 수 있는 칸에 양이 있으면 
						 * 울타리를 어떻게 설치해도 늑대가 양이있는 칸에 갈 수 있는 경우
						 */
						if(map[nx][ny]=='S')
							flag=false;
						
						/*
						 * 늑대가 이동할 수 있는 칸에 양들이 없고
						 * 늑대의 상,하,좌,우 모든 칸에 울타리를 설치한다면 
						 * 늑대는 절대로 양이 있는 칸으로 갈 수 없다. 
						 */
						if(map[nx][ny]=='.')
							map[nx][ny]='D';
					}
				}
			}
		}
		
		// 울타리를 어떻게 설치해도 늑대가 양이있는 칸에 갈 수 있는 경우
		if(flag==false)
			System.out.println(0);
		// 아니라면 맵 출력
		else {
			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();	
			}
				
		}
	}

}

 

[고찰]

 이번 문제는 설치할 수 있는 울타리의 개수가 최소가 되게하는 문제가 아니라서 난이도가 낮은 것 같다. 위의 코드는 늑대의 주변에 울타리를 설치하여 늑대가 양에게 접근할 수 없도록 한 것이다. 이때 인접한 칸으로 이동할 수 있는 늑대가 양이 있는 칸으로 이동할 수 없는 경우는 인접한 칸에 양이 없는 경우이다. 즉, 늑대가 있는 칸의 상, 하, 좌, 우 칸들을 탐색했을 때 양이 있다면 해당 경우는 울타리를 어떻게 설치해도 늑대가 양에 접근할 수 있다. 

 해당 문제에 울타리의 개수의 최솟값을 구하라고 제시했다면 좀 더 어려운 문제가 됐을 것 같다.