[백준] 10026 적록색약

문제 출처: www.acmicpc.net/problem/10026

10026번: 적록색약

: 주어진 색 정보를 적록색약이 아닌 사람이 볼 때 몇개의 구역으로 나누어지는지 구해야 하고

: 적록색약인 사람이 볼 때 몇개의 구역으로 나누어질 수 있는지 구해야 한다.

 

: dfs 방식으로 접근할 수 있다.

: 우선 처음 시작한 색과 같은 색이면 계속해서 탐색을 하고 만약 다른 색이면 처음으로 돌아와 끊어졌던 지점부터 다시 색 정보를 갱신해서 탐색할 수 있도록 한다.

: 적록색약인 사람과 적록색약이 아닌 사람의 함수를 각각 만들었는데 다른 점은 그냥 어떤색들을 같은 색으로 봐야하는지이다.

: 적록색약인 경우에는 R과 G를 하나의 색으로 봐야하기 때문에 이 부분에 해당하는 조건문을 하나 추가해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static char[][] map;
	static boolean[][] v;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// N*N의 행렬을 나타내는 N을 입력받고
		N = Integer.parseInt(br.readLine());
		
		// N*N 행렬을 만들어서
		map = new char[N][N];
		
		// 그 내용을 입력받고
		for(int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split("");
			for(int j = 0; j < N; j++) {
				map[i][j] = tmp[j].charAt(0);
			}
		}
//		for(char[] sub : map)
//			System.out.println(Arrays.toString(sub));
		// dfs 방식으로 구함
		setRGB();
		System.out.println(sb);
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int RGBCnt = 0;
	static int RGCnt = 0;
	private static void setRGB() {
		
		// 적록색약이 아닌 사람이 봤을 때와
		RGBCnt = 0;
		v = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!v[i][j]) {
					RGBCnt++;
					RGB(i,j, map[i][j]);
				}
			}
		}
		sb.append(RGBCnt + " ");
		// 적록색약인 사람이 봤을 때 영역 수를
		RGCnt = 0;
		v = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!v[i][j]) {
					RGCnt++;
					RG(i,j, map[i][j]);
				} 
			}
		}
		sb.append(RGCnt);
	}
	private static void RGB(int r , int c, char ch) {
		for(int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc]) continue;
			if(map[nr][nc] == map[r][c]) {
				v[nr][nc] = true;
				RGB(nr, nc, map[nr][nc]);				
			}
		}
		
	}
	private static void RG(int r, int c, char ch) {
		// TODO Auto-generated method stub
		for(int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc]) continue;
			if(map[nr][nc] == map[r][c] || (map[nr][nc] == 'R' && map[r][c] == 'G')
					|| (map[nr][nc] == 'G' && map[r][c] == 'R')) {				
				v[nr][nc] = true;
				RG(nr, nc, map[nr][nc]);
			} 
		}
	}
	
}