백준 3187 양치기 꿍 (Java)

1. 문제 링크

3187번: 양치기 꿍

 

2. 문제 및 입출력예제

 

3. 문제 풀이

모든 곳을 돌면서 방문하지 않은 곳 중 양이나 늑대가 있는 곳에서 양의 수와 늑대의 수를 0으로 초기화하고 BFS 탐색을 한다.

시작 지점을 큐에 넣고 BFS 탐색을 시작한다.

큐에서 뺀 곳이 늑대일 경우 늑대의 값을 증가하고, 양일 경우 양의 수를 증가한다.

BFS를 끝내고 다시 왔을 때, 양이 많으면 양만 살아남고, 나머지의 경우에는 늑대만 살아남는다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int N, M, s, w;
	static char[][] map;
	static boolean[][] visit;
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
    
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		
		map = new char[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		int sheep = 0, wolf = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				//방문하지 않은 곳 중에서 양이나 늑대가 있는 곳
				if(!visit[i][j] && (map[i][j]=='v' || map[i][j] == 'k')) {
					//값 초기화
					s = 0;
					w = 0;
					bfs(i, j);
					if(s>w) { //양이 많으면 양만 살아남음
						sheep += s;
					}
					else {
						wolf += w;
					}
				}
			}
		}
		System.out.println(sheep+" "+wolf);
	}
	
	private static void bfs(int i, int j) {		
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[]{i, j});
		visit[i][j] = true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			int x = now[0];
			int y = now[1];
			if(map[x][y] == 'v') { //늑대일 경우
				w++;
			}
			else if(map[x][y] == 'k') { //양일 경우
				s++;
			}
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				if(X<0 || X>=N || Y<0 ||Y>=M ||visit[X][Y] ||map[X][Y] == '#') {
					continue;
				}
				queue.offer(new int[] {X, Y});
				visit[X][Y] = true;
			}
		}
	}
	
}