[백준] 16956 - 늑대와 양 (Java)

[백준] 16956 - 늑대와 양 (Java)

문제

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

풀이/후기

스페셜 저지 문제로, 예제에 나온 출력과 내 결과가 달라도 문제의 조건이 맞다면 정답처리가 된다.

처음 예제 출력을 보고 울타리를 어떻게 효율적으로 배치하는 코드를 짜야하는지 막막했다. 

그러나 울타리 개수가 한정된 것이 아니고, 효율적으로 배치하라는 조건도 없기 때문에

그저 양과 늑대가 만나지만 않는다면 울타리는 자유롭게 설치가 가능하다.

예제 3 출력을 보면 울타리가 하나 들어가 있는데, 어차피 늑대가 존재하지 않기 때문에 울타리가 없어도 정답이다.

 

그래서 BFS를 이용해 늑대 주변에 모두 울타리를 설치하는 방식으로 풀었다.

단, 늑대와 양이 1칸 이내에 존재한다면 무조건 만나기 때문에

바로 0을 반환, 모든 로직을 종료하고 결과를 출력한다.

코드

package GraphTheory;

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

public class Problem16956 {
	
	static int R, C;
	static int[][] map;
	static boolean[][] visited;
	static int[][] dir = {{-1,0}, {1,0}, {0,1}, {0,-1}};
	static Queue<int[]> q = new LinkedList<>();
	static int result = 1;
	
	public static void main (String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(str.nextToken());
		C = Integer.parseInt(str.nextToken());
		
		map = new int[R][C];
		visited = new boolean[R][C];
		
		for (int i=0; i<R; i++) {
			String[] inp = br.readLine().split("");
			for (int j=0; j<C; j++) {
				int in = 0;
				if (inp[j].equals("S")) {
					in = 1;
				} else if (inp[j].equals("W")) {
					in = 2;
				}
				map[i][j] = in;
			}
		}
		
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				if (map[i][j] == 2) {
					bfsFn(i,j);
					if (result == 0) {
						break;
					}
				}
			}
		}
		
		System.out.println(result);
		StringBuilder sb = new StringBuilder();
		if (result == 1) {
			for (int i=0; i<R; i++) {
				for (int j=0; j<C; j++) {
					if (map[i][j] == 0) {
						sb.append(".");
					}
					if (map[i][j] == 1) {
						sb.append("S");
					}
					if (map[i][j] == 2) {
						sb.append("W");
					}
					if (map[i][j] == 3) {
						sb.append("D");
					}
				}
				sb.append("\n");
			}
			System.out.println(sb);
		}
		
	}
	
	static void bfsFn(int x, int y) {
		q.add(new int[] {x,y});
		visited[x][y] = true;
		
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];
			
			for (int i=0; i<4; i++) {
				int nx = cx + dir[i][0];
				int ny = cy + dir[i][1];
				
				if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
					continue;
				}
				
				if (visited[nx][ny]) {
					continue;
				}
				
				if (map[nx][ny] == 2) {
					continue;
				}
				
				if (map[nx][ny] == 3) {
					continue;
				}
				
				//1칸 내에 양이 있는 경우 바로 종료
				if (map[nx][ny] == 1) {
					result = 0;
					return;
				}
				
				if (map[nx][ny] == 0) {
					map[nx][ny] = 3;
					visited[nx][ny] = true;
				}
			}
		}
	}
}

Commit

https://github.com/allrightDJ0108?tab=overview&from=2023-03-01&to=2023-03-10

참고