BOJ_16956_늑대와 양

1. 

구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 애드 혹,구성적 
언어: Java
전략: 
BFS를 통해 전체 그래프를 탐색하면서 늑대가 이동해서 갈 수 있는 곳을 막는다.

늑대를 기준으로(늑대를 큐에 넣어) 늑대와 인접하고, 또 그 것이 양과 인접하는지 찾아서 그 곳을 울타리로 막는다

1. 인접한 것이 S - 내가 '.' 이면 D삽입 / 내가 W면 답이 없음

2. 인접한 것이 '.' 이면 큐에 삽입

3. 인접한 것이 W면 지나가  

---

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	
	static class Node{
		int y; 
		int x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//높이와 너비 
		int h = scanner.nextInt();
		int w = scanner.nextInt();
		
		Queue<Node> q = new LinkedList<>();
		
		//양과 늑대 배열을 받을 문자형 배열
		char[][] map = new char[h][w];
		//방문여부를 확인하는 boolean
		boolean[][] check = new boolean[h][w];
		for(int i = 0; i<h; i++) {
			String str = scanner.next();
			for(int j = 0; j<w; j++) { 
				map[i][j]= str.charAt(j);
				if(map[i][j] == 'W') { //늑대는 일단 뷰에 넣고, 방문 처리
					q.offer(new Node(i,j));
					check[i][j] = true;
				}
			}
		}
		//4방 탐색
		int[] dx = {1,-1,0,0};
		int[] dy = {0,0,1,-1};
		
		boolean isok = true;
		
		loop:while(!q.isEmpty()) {
			Node node = q.poll();
			int px = node.x;
			int py = node.y;
			
			for(int d = 0; d<4; d++) {
				int nx = px + dx[d];
				int ny = py + dy[d];
				
				//범위를 살핀다.
				if(nx<0 || ny<0 || nx>=w || ny>=h)continue;

				//늑대면 그냥 패스 
				if(map[ny][nx]=='W') continue;
				
				//방문한 적이 없고, .인 경우 - 큐에 삽입
				if(!check[ny][nx]&&map[ny][nx]=='.') {
					q.offer(new Node(ny, nx));
					check[ny][nx] = true;
				}
				//인접한게 양인 경우 
				if(!check[ny][nx] && map[ny][nx]=='S') {
					//만약 이떄 내가 원래 늑대였으면 끝! - 노답
					if(map[py][px]=='W') {
						isok = false;
						break loop;
					}//근데 내가 .이야 그럼 이곳에 울타리 설치 
					if(map[py][px]=='.')
						map[py][px] = 'D';
					q.offer(new Node(ny, nx));
					check[ny][nx] = true;
				}				
			}//4방탐색			
		}//while문
		
		if(!isok) System.out.println(0); //노답이면 0 출력
		else {//아니면 전체 배열 출력
			System.out.println(1);
			for(int i = 0; i<h; i++) {
				for(int j = 0; j<w; j++) {
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			
		}
		

	}//main

}

---

3

• 어떤 방식으로 늑대를 울타리로 막으면 된다.
• 테스트 케이스와 답이 계속 달라 많이 고민했지만, 문제에 최소의 개수로 울타리를 두는게 아니라 했기 때문에 완벽한 정답은 없다. (테스트 케이스에도 늑대가 없는데 울타리를 설치하기도 했다.)
• 다만 최적화를 시키는 방법을 찾아야 한다. (최소한의 울타리 사용)