백준 3184: 양

문제보기
Alt text

풀이

DFS 이용

소스코드

import java.util.Scanner;

public class Main {
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int R, C, sheep, wolf;
	static int[][] map;
	static boolean[][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new int[R][C];
		visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			String str = sc.next();
			for (int j = 0; j < C; j++) {
				char ch = str.charAt(j);
				if (ch == '.')
					map[i][j] = 0;
				else if (ch == '#')
					map[i][j] = 1;
				else if (ch == 'v')
					map[i][j] = 99;
				else if (ch == 'o')
					map[i][j] = -1;
			}
		}

		int ans_sheep = 0;
		int ans_wolf = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (!visited[i][j]) {
					if (map[i][j] == 0 || map[i][j] == 99 || map[i][j] == -1) {
						if (map[i][j] == 0) {
							sheep = 0;
							wolf = 0;
						}
						else if (map[i][j] == 99) {
							sheep = 0;
							wolf = 1;
						}else if (map[i][j] == -1) {
							sheep = 1;
							wolf = 0;
						}
						dfs(i, j);

						// 여기까지 같은 영역을 구했어
						// 양의 수와 늑대 수를 계산하자
						if (sheep > wolf) {
							ans_sheep += sheep;
						} else {
							ans_wolf += wolf;
						}
					}
				}
			}
		}

		System.out.println(ans_sheep+" "+ans_wolf);
	}

	static void dfs(int r, int c) {
		visited[r][c] = true;
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];

			if (nr >= 0 && nc >= 0 && nr < R && nc < C && !visited[nr][nc]) {
				if (map[nr][nc] == 0) {
					dfs(nr, nc);
				} else if (map[nr][nc] == -1) {
					sheep++;
					dfs(nr, nc);
				} else if (map[nr][nc] == 99) {
					wolf++;
					dfs(nr, nc);
				}
			}
		}
	}
}