[BOJ] 백준 10026번 적록색약 (Java)

#10026 적록색약

난이도 : 골드 5

유형 : 그래프 탐색 / DFS

10026번: 적록색약

▸ 문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

▸ 출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

 

 

문제 풀이  

주어진 그래프를 두가지 케이스 (적록색약 o,x)로 나눠서 구역의 수를 구하는 문제이디.

 

📚 조건

• N ( 1<= N <= 100)
• 그래프1 (R,G,B), 그래프2(R==G,B)

 

구상

1. map을 두가지 케이스로 (R,G,B) 맵을 입력받아 DFS탐색을 통해 해당 영역이 몇 개의 영역으로 나누어져 있는지 조사한다.

2. 1번의 그래프를 (R==G,B)맵으로 바꿔주고 해당 맵을 다시 DFS탐색을 통해 조사한다.

 

 

스케치

1번 로직

2차 배열에 으로 입력받고 각 구역을 DFS로 탐색해준다.

for(int i=0; i<n; i++) {
	String[] color = br.readLine().split("");
	for(int j=0; j<n; j++) {
		if(color[j].equals("R")) {
			map[i][j] = 1;
		}else if(color[j].equals("G")) {
			map[i][j] = 2;
		}else {
			map[i][j] = 3;
		}
	}
}

for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) {
		for(int k=1; k<4; k++) {
			if(!checked[i][j] && map[i][j] == k) {
				dfs(i,j,k);
				cnt++;
			}
		}
	}
}

 

2번 로직

적록색약 그래프 (R: 1 == G: 2), B: 3를 만들어준 다음 이 또한 DFS로 탐색해주면 된다.

for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) {
		if(map[i][j] ==1 ) {
			map[i][j] = 2;
		}
	}
}

checked = new boolean[n][n];
for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) {
		for(int k=2; k<4; k++) {	
			if(!checked[i][j] && map[i][j] == k) {
				dfs(i,j,k);
				rgCnt++;
			}
		}
	}
}

 

 

풀이 코드

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

public class Main {

	static int n;
	static int[][] map;
	static boolean[][] checked;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,-1,0,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		checked = new boolean[n][n];
		int cnt=0;
		int rgCnt=0;
		
		for(int i=0; i<n; i++) {
			String[] color = br.readLine().split("");
			for(int j=0; j<n; j++) {
				if(color[j].equals("R")) {
					map[i][j] = 1;
				}else if(color[j].equals("G")) {
					map[i][j] = 2;
				}else {
					map[i][j] = 3;
				}
				
			}
		}
		
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				for(int k=1; k<4; k++) {
					if(!checked[i][j] && map[i][j] == k) {
						dfs(i,j,k);
						cnt++;
					}
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(map[i][j] ==1 ) {
					map[i][j] = 2;
				}
			}
		}
		
		checked = new boolean[n][n];
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				for(int k=2; k<4; k++) {
					if(!checked[i][j] && map[i][j] == k) {
						dfs(i,j,k);
						rgCnt++;
					}
				}
			}
		}
		System.out.println(cnt+" "+rgCnt);
		
		
	}
	
	static void dfs(int x, int y, int color) {
		
		checked[x][y] = true;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <0 || ny <0 || nx>n-1 || ny>n-1) continue;
			if(checked[nx][ny]) continue;
			
			if(map[nx][ny] == color) {
				dfs(nx,ny, color);
			}
		}
		
	}
}