적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB GGBBB BBBRR BBRRR RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제 입력 1복사
5 RRRBB GGBBB BBBRR BBRRR RRRRR
예제 출력 1복사
4 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static int x, y;
static ArrayList<int[]>[] graph;
static boolean[][] visit; // 이미 방문한 정점의 정보를 담을 배열
static Queue<int[]> Q;
static char[][] map;
static int[][] deltas = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
static int c = 0;
static int RG_c = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visit = new boolean[N][N];
for (int n = 0; n < N; n++) {
map[n] = br.readLine().toCharArray();
}
graph = new ArrayList[N * N];
for (int i = 0; i < N * N; i++) {
graph[i] = new ArrayList<int[]>();
}
// 인접 그래프 만들기 (=ok)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 4; k++) {
int nr = deltas[k][0] + i;
int nc = deltas[k][1] + j;
int[] n = { nr, nc };
if (nr < 0 || nc < 0 || nr >= N || nc >= N)
continue;
graph[i * N + j].add(n);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, true);
c++;
}
}
}
sb.append(c + " ");
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, false);
RG_c++;
}
}
}
sb.append(RG_c);
System.out.println(sb);
}
private static void bfssol(int[] p, boolean b) {
Q = new LinkedList<int[]>();
// 시작정점을 큐에 넣어줌
Q.add(p);
// 시작정점을 방문했다는 정보 저장
visit[p[0]][p[1]] = true;
// 큐에 정점이 없어질 때까지 반복
while (!Q.isEmpty()) {
// 큐에서 정점을 poll해서 이동함
int[] q = Q.poll();
// 이동한 정점에서 연결된 정점들을 큐에 넣어주고 visit배열에 체크
for (int[] i : graph[q[0] * N + q[1]]) {
if (b) {
if (!visit[i[0]][i[1]] && map[q[0]][q[1]] == map[i[0]][i[1]]) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
} else {
if (!visit[i[0]][i[1]] && ((map[q[0]][q[1]] == 'R' && map[i[0]][i[1]] == 'G')
|| (map[q[0]][q[1]] == 'G' && map[i[0]][i[1]] == 'R')
|| map[q[0]][q[1]] == map[i[0]][i[1]])) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
}
}
}
}
}
