boj)10026 - 적록색약
2020. 10. 21. 17:07ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_10026 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N, nx, ny, ans1, ans2;
static char c;
static char[][] map = new char[101][101];
static boolean[][] v = new boolean[101][101];
static Queue<int[]> q = new LinkedList<>();
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!v[i][j]) {
c = map[i][j];
v[i][j] = true;
q.offer(new int[]{i, j});
ans1++;
}
bfs(v);
}
}
boolean[][] v2 = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!v2[i][j]) {
c = map[i][j];
v2[i][j] = true;
q.offer(new int[]{i, j});
ans2++;
}
if (c == 'R' || c == 'G') {
while (!q.isEmpty()) {
int[] now = q.poll();
for (int k = 0; k < 4; k++) {
nx = now[0] + dx[k];
ny = now[1] + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (!v2[nx][ny] && (map[nx][ny] == 'R' || map[nx][ny] == 'G')) {
v2[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
} else {
bfs(v2);
}
}
}
System.out.println(ans1 + " " + ans2);
}
private static void bfs(boolean[][] v) {
while (!q.isEmpty()) {
int[] now = q.poll();
for (int k = 0; k < 4; k++) {
nx = now[0] + dx[k];
ny = now[1] + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (!v[nx][ny] && map[nx][ny] == c) {
v[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
- 2가지 방법으로 나눠서 각자 bfs 따로 돌려줌
'PS > boj' 카테고리의 다른 글
boj)1629 - 곱셈 (0) | 2020.10.23 |
---|---|
boj)2468 - 안전 영역 (0) | 2020.10.21 |
boj)7569 - 토마토 (0) | 2020.10.19 |
boj)1697 - 숨바꼭질 (0) | 2020.10.17 |
boj)4179 - 불! (0) | 2020.10.17 |