백준 3187번 : 양치기 꿍

 문제

www.acmicpc.net/problem/3187

3187번: 양치기 꿍

3187 양치기 꿍

 

 구현 방법

 bfs로 구현했습니다. 맴 전체를 탐색하며 #(울타리)가 아닐때마다 bfs를 돌려 양과, 늑대 수를 카운팅 해주었습니다.

주의할 점은 딱 한 칸 존재하는데 그 칸이 빈 칸이 아니라 늑대, 양 일수도 있으므로 bfs 돌리기 전 카운팅을 진행해줘야 합니다.

 

3184번 : 양이랑 거의 똑같은 문제입니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ3187_양치기꿍 {
	static int R, C, sheep, wolf, totalS, totalW;
	static char[][] map;
	static int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<int[]> bfs;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			map[r] = input.toCharArray();
		}
		// 입력완료
		bfs = new LinkedList<>();
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]!='#') {
					sheep = 0; wolf = 0; // 양, 늑대 값 초기화
					trans(r, c);
					bfsL();
				}
			}
		}
		System.out.println(totalS+" "+totalW);
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			int[] now = bfs.poll();
			for (int d=0;d<4;d++) {
				int nr = now[0]+deltas[d][0];
				int nc = now[1]+deltas[d][1];
				if (isIn(nr, nc) && map[nr][nc]!='#') trans(nr, nc);
			}
		}
		if (wolf>=sheep) totalW += wolf; // 늑대 수가 크거나 같으면 양은 다 잡아먹힘
		else totalS += sheep; // 양의 수가 더 크면 늑대는 다 잡아먹힘
	}
	
	static void trans(int r, int c) {
		if (map[r][c]=='v') wolf++; 
		else if (map[r][c]=='k') sheep++;
		map[r][c] = '#'; // 방문체크
		bfs.offer(new int[] {r, c});
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!