[BaekJoon] 10026 적록색약

1.  문제 링크

https://www.acmicpc.net/problem/10026

2.  문제

요약

• 크기가 N X N인 그리드의 각 칸에 R, G, B 중 하나를 색칠한 그림이 있고 그림은 같은 색으로 이루어져 있는 구역들로 나뉘어져 있습니다.
• 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속합니다.(색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라고 합니다.)
• 그림이 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때의 구역의 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 N이 주어지고 두 번째 줄부터 N개의 줄에는 그림이 주어집니다.
• 출력: 첫 번째 줄에 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int num;
	static char[][] painting;
	boolean[][] visited;
	public void dfs(int x, int y, char color) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < num && cy >= 0 && cy < num) {
				if(!visited[cx][cy] && painting[cx][cy] == color) {
					dfs(cx, cy, color);
				}
			}
		}
	}
	
	public void dfs(int x, int y, char color, char color2) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < num && cy >= 0 && cy < num) {
				if(!visited[cx][cy] && (painting[cx][cy] == color || painting[cx][cy] == color2)) {
					dfs(cx, cy, color, color2);
				}
			}
		}
	}
	
	public int[] getNumOfArea() {
		int[] counts = new int[2];
		visited = new boolean[num][num];
		char[] color = {'R', 'G', 'B'};
		for(int i = 0; i < color.length; i++) {
			for(int j = 0; j < num; j++) {
				for(int l = 0; l < num; l++) {
					if(!visited[j][l] && painting[j][l] == color[i]) {	
						counts[0]++;
						dfs(j, l, color[i]);
					}
				}
			}
		}
		visited = new boolean[num][num];
		for(int i = 1; i < color.length; i++) {
			if(i == 1) {
				for(int j = 0; j < num; j++) {
					for(int l = 0; l < num; l++) {
						if(!visited[j][l] && (painting[j][l] == color[1] || painting[j][l] == color[0])) {	
							counts[1]++;
							dfs(j, l, color[1], color[0]);
						}
					}
				}
			} else {				
				for(int j = 0; j < num; j++) {
					for(int l = 0; l < num; l++) {
						if(!visited[j][l] && painting[j][l] == color[i]) {	
							counts[1]++;
							dfs(j, l, color[i]);
						}
					}
				}
			}
		}
		return counts;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		painting = new char[num][num];
		for(int i = 0; i < num; i++) {
			String input = br.readLine();
			for(int j = 0; j < num; j++) {
				painting[i][j] = input.charAt(j);
			}
		}
		br.close();
		Main m = new Main();
		int[] result = m.getNumOfArea();
		for(int i = 0; i < result.length; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• R, G, B를 모두 구분할 수 있는 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 R, G를 구분하지 못하는 적록색약인 사람이 봤을 때의 구역의 개수를 각각 따로 구합니다.
• 적록색약이 아닌 사람의 경우, 그림의 각 부분을 방문하였는지를 나타내는 2차원 배열 visited를 생성하고 R, G, B 각각일 때에 그림의 모든 부분을 돌면서 아직 해당 부분을 방문하지 않았고 해당 부분이 각 색깔일 때, 상하좌우를 확인하면서 해당 색깔의 영역을 확인하고 영역의 개수를 구합니다.
• 이 때, R, G, B를 모두 구분할 수 있으므로 R, G, B 모든 색상에 대해서 진행한 것입니다.
• 적록색약인 사람의 경우, 그림의 각 부분을 방문하였는지를 나타내는 2차원 배열 visited를 생성하고 R/G, B 각각일 때에 그림의 모든 부분을 돌면서 아직 해당 부분을 방문하지 않았고 해당 부분이 각 색깔일 때, 상하좌우를 확인하면서 해당 색깔의 영역을 확인하고 영역의 개수를 구합니다.
• 이 때, R과 G를 구분할 수 없기 때문에 같은 색깔이라고 보고, R 또는 G인 영역과 B인 영역을 구합니다.

1. 그림을 나타내는 2차원 배열 painting을 생성하고 주어진 그림을 해당 배열에 설정합니다.
2. 그림의 각 부분을 방문했는지 나타내는 2차원 배열 visited를 생성합니다.
3. R, G, B 각각의 색상에 대해 반복문을 돌면서 적록색약이 아닌 사람이 봤을 때의 구역의 개수를 구합니다.
   1. 그림의 모든 부분을 확인하면서 아직 해당 부분을 방문하지 않았고 해당 부분의 색깔이 해당 색깔일 경우 영역의 개수를 1 증가시키고 해당 색깔에 대한 영역을 구합니다.
      1. 상하좌우를 나타낼 dx, dy 배열을 생성하고 값을 설정하며 해당 위치를 방문했다는 의미로 해당 위치의 visited 값을 true로 변경합니다.
      2. 해당 위치의 상하좌우를 방문하여 해당 위치가 N X N 2차원 배열 내에 있고 아직 방문되지 않았으며 해당 위치의 색깔이 해당 색깔이라면 해당 위치에서 다시 상하좌우를 확인하여 구역을 구합니다.
4. 그림의 각 부분을 방문했는지 나타내는 2차원 배열 visited를 초기화합니다.
5. R 또는 G, B 각 색상에 대해 반복문을 돌면서 적록색약인 사람이 봤을 때의 구역의 개수를 구합니다.
   1. 그림의 모든 부분을 확인하면서 아직 해당 부분을 방문하지 않았고 해당 부분의 색깔이 해당 색깔일 경우 영역의 개수를 1 증가시키고 해당 색깔에 대한 영역을 구합니다. 이 때, R과 G를 구분할 수 없으므로 R과 G는 같은 색깔이라고 생각하고 B에 해당하는 영역과 나머지 영역을 구합니다.
      1. 상하좌우를 나타낼 dx, dy 배열을 생성하고 값을 설정하며 해당 위치를 방문했다는 의미로 해당 위치의 visited 값을 true로 변경합니다.
      2. 해당 위치의 상하좌우를 방문하여 해당 위치가 N X N 2차원 배열 내에 있고 아직 방문되지 않았으며 해당 위치의 색깔이 해당 색깔이라면 해당 위치에서 다시 상하좌우를 확인하여 구역을 구합니다.
6. 이렇게 구한 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 개수를 출력합니다.