양
백준 3184: 양
풀이
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);
}
}
}
}
}