Baekjoon_10026 - 적록색약
문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
해결방법
- BFS를 이용해서 해결했다.
Person클래스를 만들어, 적록색맹의 여부에 따른 사람 객체를 만들기로 했다.Person클래스는 각각 그림을 의미하는arr와 그림의 색상에 따른 영역의 개수를 의미하는cnt필드를 가지고 있다.- 그리고 생성자에서 적록색맹 여부를 받아와 (
isRedGreenBlindness) 적록색맹이라면arr에 있는 빨간색(R) 부분을 모두 초록색(G)으로 바꿔서 필드에 넣었다.
- 적록색맹이 아닌
p1과 적록색맹인p2객체를 생성해 각각 BFS를 돈다.isVisited배열을 만들어 방문 여부를 체크하면서 돈다.- BFS를 돌 때마다 각각의
cnt를 하나씩 더해가며 총 몇개의 영역이 있는지 알아낸다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Baekjoon_10026 {
static int n;
static char[][] arr;
static boolean[][] isVisited;
static Deque<int[]> dq;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new char[n][n];
isVisited = new boolean[n][n];
for (int i = 0; i < n; i++) {
String tmpStr = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = tmpStr.charAt(j);
}
}
char[][] arr1 = getCopyArr(arr);
char[][] arr2 = getCopyArr(arr);
Person p1 = new Person(arr1, false);
Person p2 = new Person(arr2, true);
executeBfs(p1);
isVisited = new boolean[n][n];
executeBfs(p2);
System.out.println(p1.cnt + " " + p2.cnt);
}
public static void executeBfs(Person p2) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!isVisited[i][j]){
bfs(i, j, p2.arr);
p2.cnt++;
}
}
}
}
public static void bfs(int x, int y, char[][] arr){
dq = new ArrayDeque<>();
int[] pos = {x,y};
dq.add(pos);
isVisited[x][y] = true;
while(!dq.isEmpty()){
int[] tmp = dq.poll();
x = tmp[0];
y = tmp[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n){
continue;
}
if(isVisited[nx][ny]){
continue;
}
if(arr[x][y] != arr[nx][ny]){
continue;
}
if(arr[x][y] == arr[nx][ny]){
isVisited[nx][ny] = true;
int[] tmp2 = {nx, ny};
dq.add(tmp2);
}
}
}
}
public static char[][] getCopyArr(char[][] arr){
char[][] copyArr = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
copyArr[i][j] = arr[i][j];
}
}
return copyArr;
}
static class Person{
char[][] arr;
int cnt = 0;
public Person(char[][] arr, boolean isRedGreenBlindness) {
if(isRedGreenBlindness){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(arr[i][j] == 'R'){
arr[i][j] = 'G';
}
}
}
}
this.arr = arr;
}
}
}이번 문제를 풀며 배열의 복사에 대해 다시금 공부할 수 있게 되었다.
각 객체의
arr배열은 모두 독립적으로 다뤄져야 하므로, 입력값으로 들어온 배열을 복사해서 생성자의 매개변수로 넘겨줄 필요가 있었다. 따라서 당연하게arr.clone()을 사용했는데 생각한대로 출력이 되지 않아서 좀 해맸던것 같다.알고보니 이차원 배열에서의 깊은 복사에서는
clone()메서드를 사용할 수 없었다.배열의 얕은 복사와 깊은 복사에 관한 자세한 정리는 여기서 확인할 수 있다.
