# BOJ10026 적록색약
https://www.acmicpc.net/problem/10026 (opens new window)
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N x N인 그리드의 각 칸에 RGB중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
# Location
좌표 관리를 위한 location 클래스이다.
private static class Location {
private final int x;
private final int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
# 너비 우선 탐색
BFS를 활용하여 풀이하였다. 특정한 색을 너비 우선 탐색을 진행하며 방문 기록을 남겼다.
private static void bfs(int x, int y, String color) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y, color)) {
queue.add(new Location(x, y));
visited[x][y] = true;
}
}
}
}
# 제출 코드
적록색약이 아닌 사람은 모든 RGB를 볼 수 있기 때문에 전부 BFS로 탐색한다.
int noneBlindness = 0; // 적록색약이 아닌 사람
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("R") && !visited[i][j]) {
bfs(i, j, "R");
noneBlindness++;
} else if (graph[i][j].equals("G") && !visited[i][j]) {
bfs(i, j, "G");
noneBlindness++;
} else if (graph[i][j].equals("B") && !visited[i][j]) {
bfs(i, j, "B");
noneBlindness++;
}
}
}
적록색약인 사람은 RG를 구별할 수 없기 때문에 G를 R로 전부 바꾸고 방문 기록을 초기화한 뒤 다시 한번 탐색을 진행한다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("G")) {
graph[i][j] = "R";
}
}
}
visited = new boolean[n][n];
int blindness = 0; // 적록색약인 사람
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("R") && !visited[i][j]) {
bfs(i, j, "R");
blindness++;
} else if (graph[i][j].equals("B") && !visited[i][j]) {
bfs(i, j, "B");
blindness++;
}
}
}
아래는 최종 제출 코드이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BOJ10026 {
private static int n;
private static String[][] graph;
private static boolean[][] visited;
private static final int[] dx = {-1, 0, 1, 0};
private static final int[] dy = {0, 1, 0, -1};
private static class Location {
private final int x;
private final int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
private static void bfs(int x, int y, String color) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y, color)) {
queue.add(new Location(x, y));
visited[x][y] = true;
}
}
}
}
private static boolean isLocation(int x, int y, String color) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || !graph[x][y].equals(color)) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
graph = new String[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
String[] colors = scanner.next().split("");
for (int j = 0; j < n; j++) {
graph[i][j] = colors[j];
}
}
int noneBlindness = 0; // 적록색약이 아닌 사람
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("R") && !visited[i][j]) {
bfs(i, j, "R");
noneBlindness++;
} else if (graph[i][j].equals("G") && !visited[i][j]) {
bfs(i, j, "G");
noneBlindness++;
} else if (graph[i][j].equals("B") && !visited[i][j]) {
bfs(i, j, "B");
noneBlindness++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("G")) {
graph[i][j] = "R";
}
}
}
visited = new boolean[n][n];
int blindness = 0; // 적록색약인 사람
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j].equals("R") && !visited[i][j]) {
bfs(i, j, "R");
blindness++;
} else if (graph[i][j].equals("B") && !visited[i][j]) {
bfs(i, j, "B");
blindness++;
}
}
}
System.out.println(noneBlindness + " " + blindness);
}
}