[백준] 3187 양치기 꿍 - BFS(넓이우선탐색) JAVA

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

코드설명

 BFS(넓이우선탐색) 를 활용하면됩니다.

 

https://passionfruit200.tistory.com/1450

[백준] 3184 양 - BFS(넓이우선탐색) JAVA

이전에 풀었던 1450 문제와 같습니다.

차이점은 양이 'o'가 아니라 'k' 로 바뀌었습니다.

 

문제에서 주어지듯, 마당에서 "탈출"할 수 있는 칸일 경우 어떤 영역에도 속하지 않는다고 가정합니다.

그러므로, 저는 바깥에 마당으로 나올 수 있게 빈필드를 새로 추가했습니다.

matrix = new char[N + 2][M + 2];

이와 같이 처리할경우 행에 + 2만큼, 열에 + 2 만큼 사이즈는 늘어납니다. 하지만 훨씬 더 쉽게 바깥과 연결된 필드를 체크할 수 있으므로 이와 같이 구현했습니다.

 

이외 각 구역의 Counting하는 것은 일반적인 BFS구현입니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	static char[][] matrix;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new char[250 + 2][250 + 2];
 
		for(int i=0; i<N+2; i++) {
			Arrays.fill(matrix[i], '.');
		}
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=1; j<=M; j++) {
				matrix[i][j] = str.charAt(j - 1);
			}
		}
 
		//먼저 밖에 연결된 칸을 모두 울타리로 바꾸어준다.
		coloringBFS(0, 0);
 
		for(int i=2; i<N; i++) {
			for(int j=2; j<M; j++) {
				if(matrix[i][j] != '#') {
					int[] temp = countSheepWolf(i, j);
					answer[0] += temp[0]; answer[1] += temp[1];
				}
			}
		}
		for(int v : answer) System.out.print(v+" ");
	}
	
	static void coloringBFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = '#';
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int[] dir : new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0}}){
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				
				if(nr < 0 || nr >= N + 2 || nc < 0 || nc >= M + 2) continue;
				if(matrix[nr][nc] == '#') continue;
				matrix[nr][nc] = '#';
				q.offer(new int[] {nr, nc});
			}
		}
	}
	
	static int[] countSheepWolf(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		int wolfCnt = 0;
		int sheepCnt = 0;
		if(matrix[sr][sc] == 'v') wolfCnt+=1;
		else if(matrix[sr][sc] == 'k') sheepCnt += 1;
		matrix[sr][sc] = '#';
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int r = temp[0], c = temp[1];
 
			for(int[] dir : new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}) {
				int nr = r + dir[0];
				int nc = c + dir[1];
				
				if(nr < 1 || nr >= N+1 || nc < 1 || nc >= M + 1) continue;
				if(matrix[nr][nc] == '#') continue;
				
				if(matrix[nr][nc] == 'v') wolfCnt+=1;
				else if(matrix[nr][nc] == 'k') sheepCnt += 1;
				matrix[nr][nc] = '#';
				q.offer(new int[] {nr, nc});
			}
		}
		
		int[] ret = new int[2];
		if(wolfCnt < sheepCnt) {
			ret[0] = sheepCnt;
		}else if(wolfCnt >= sheepCnt) {
			ret[1] = wolfCnt;
		}
		return ret;
	}
	
	
	
	
}