[문제] 백준 3184번 양

www.acmicpc.net/problem/3184

3184번: 양

내 풀이

 

bfs 함수에서 for문으로 4방 탐색 안하고 while 문에서 x,y를 업데이트하는 식으로 했는데 틀렸다!

for 문으로 4방 탐색하는게 안전한 듯 하다.

public class BOJ_3184 {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	static int R, C;
	static char[][] matrix;
	static int sheep = 0, wolf = 0;	// 최종 양과 늑대 수
	static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		R = Integer.parseInt(st.nextToken());	//세로
		C = Integer.parseInt(st.nextToken());	// 가로
		matrix = new char[R][C];
		visited = new boolean[R][C];	//방문 체크

		// init matrix
		for (int i = 0; i < R; i++) {
			String s = in.readLine();
			for (int j = 0; j < C; j++) {
				char c = s.charAt(j);
				matrix[i][j] = c;
			}
		}

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (matrix[i][j] == 'o' || matrix[i][j] == 'v') { // 양이나 늑대가 있는 시점에서 탐색
					if (!visited[i][j]) {	// 아직 방문하지 않은 영역이라면 탐색 시작
						bfs(i, j);
					}
				}
			}
		}
		// sheep, wolf 출력
		System.out.println(sheep + " " + wolf);
	}

	static void bfs(int a, int b) {
		Queue<int[]> q = new LinkedList<>();

		int s = 0, w = 0; // 해당 영역에서 양과 늑대 수 세기

		visited[a][b] = true; // (a,b) 방문

		if (matrix[a][b] == 'v')
			w++;
		else if (matrix[a][b] == 'o')
			s++;

		q.offer(new int[] { a, b });

		while (!q.isEmpty()) {

			int[] loc = q.poll();	// 현재 위치
			int x = loc[0];
			int y = loc[1];
			
			// 사방 탐색
			for (int d = 0; d < 4; d++) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				if (nx >= 0 && nx < R && ny >= 0 && ny < C && matrix[nx][ny] != '#' && !visited[nx][ny]) {
					if (matrix[nx][ny] == 'o') {
						s++;
					} else if (matrix[nx][ny] == 'v') {
						w++;
					}
					visited[nx][ny] = true;
					q.offer(new int[] { nx, ny });
				}
			}
		}
		// 양이 더 많으면 늑대 x
		if (s > w) {
			sheep+= s;
		}
		else {		// 늑대가 양보다 같거나 많으면 양 x
			wolf += w;
		}
	}
}