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

문제 Gold5

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

10026번: 적록색약

---

풀이

같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로,

깊이우선탐색을 통해 같은 구역을 확인한다.

문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|｀O′|┛

 

일반인이 보는 구역을 확인하기 위해 입력받은 배열 그대로 DFS를 돌린다.

DFS를 돌리면서, 'G'색을 만나면 해당 인덱스에 대한 연산이 모두 끝난 후 'R'로 바꿔준다.

적록색약일 때의 탐색을 위해서!

그 후, 다시 똑같은 메소드로 적록색약 DFS를 돌리고 결과를 출력한다. 

 

코드

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

public class Main{
	static int[] di = {-1,1,0,0};
	static int[] dj = {0,0,-1,1};
	static int N;
	static char[][] color;
	static boolean[][] visited;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		color = new char[N][N];
		visited = new boolean[N][N];
		int res = 0;
		for(int i =0 ; i < N ; i++) {
			String str = br.readLine();
			for(int j =0 ; j < N ; j++) {
				color[i][j] = str.charAt(j);
			}
		}
		//적록색약이 아닐 때, 구역 개수
		for(int i =0 ; i < N ; i++) {
			for(int j =0 ; j < N ; j++) {
				if(!visited[i][j]) {
					area(i,j);
					res++;
				}
			}
		}
		sb.append(res).append(" ");
		
		res = 0;
		visited = new boolean[N][N];
		//적록색약일 때, 구역 개수
		for(int i =0 ; i < N ; i++) {
			for(int j =0 ; j < N ; j++) {
				if(!visited[i][j]) {
					area(i,j);
					res++;
				}
			}
		}
		sb.append(res);
		System.out.println(sb.toString());
	}
	
	public static void area(int i, int j) {		//깊이우선탐색
		visited[i][j] = true;
		for(int d = 0; d< 4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];
			if(0<=ni && ni<N && 0<=nj && nj<N && !visited[ni][nj] && color[i][j] == color[ni][nj]) {
				area(ni, nj);
			}
		} 
		if(color[i][j] == 'G') color[i][j] = 'R';		//일반인 > 적록색약 순으로 검사하므로 일반인 검사 시에 G을 다 R로 바꿔 적록색약 검사를 위해 셋팅한다.
	}
}