[BOJ] 10026 - 적록색약 (Java)

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

1. 문제

• 크기가 N×N인 그리드가 주어지고, 그리드의 각 칸에는 R(빨강), G(초록), B(파랑) 중 하나의 색이 칠해져 있다.
  여기서, 적록색약인 사람이 봤을 때 인접한 빨강과 초록은 같은 색으로 인식한다.
• 그리드에서 적록색약이 아닌 사람과 적록색약인 사람이 보는 영역의 수를 각각 계산하는 문제
  

2. Idea

• 아이디어 내용

3. 풀이

3.1. 변수 입력

• N: 그리드의 크기
• 그리드 정보 입력

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new char[n+1][n+1];
visits = new boolean[n+1][n+1];

for (int i=0; i<n; i++){
	s = sc.next(); 
	for (int j=0; j<n; j++){
		map[i][j] = s.charAt(j);
	}
}

3.2. dfs 함수 구현

• DFS 탐색을 수행하는 함수
• 시작점부터 같은 색으로 이루어진 영역을 찾아 visits 배열에 방문 여부를 표시한다.

    public static void dfs(int x, int y){
        visits[x][y] = true;
        char tmp_char = map[x][y]; // R
        for(int i=0; i<4; i++){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
 
            if (new_x<0 || new_y<0 || new_x>n || new_y>n){continue;}
            if (!visits[new_x][new_y] && map[new_x][new_y] == tmp_char){dfs(new_x, new_y);}
        }
    }

3.3. dfs 탐색 수행

• 일반인이 보는 경우와 적록색약인 사람이 보는 경우에 대해 각각 DFS 탐색을 수행
  • DFS 탐색은 그리드 내에서 같은 색으로 이루어진 영역을 찾는 과정이 됨.

        // normal 인 경우
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visits[i][j]){dfs(i,j); cnt++;}
            }
        }
        int normal_cnt = cnt;
        cnt=0;
        visits = new boolean[n+1][n+1];
 
 		// dltonism 인 경우
        // G를 R로 바꿔주고 수행
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j]=='G'){map[i][j] = 'R'; // G를 R로 바꿔준다.}
            }
        }
 
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visits[i][j]){dfs(i,j); cnt++;}
            }
        }
        int abnormal_cnt = cnt;

3.4. 결과 출력

• DFS 탐색을 통해 찾은 영역의 수를 세어 출력

System.out.println(normal_cnt + " " + abnormal_cnt);

4. 전체코드

import java.util.*;
 
public class Main {
 
    static int n;
    static String s;
    static char map[][];
    static boolean visits[][];
    static int dx[] = {-1,0,0,1};
    static int dy[] = {0,1,-1,0};
 
    public static void main(String args[]) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new char[n+1][n+1];
        visits = new boolean[n+1][n+1];
 
        for (int i=0; i<n; i++){
            s = sc.next(); 
            for (int j=0; j<n; j++){
                map[i][j] = s.charAt(j);
            }
        }
 
        // normal 인 경우
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visits[i][j]){dfs(i,j); cnt++;}
            }
        }
        int normal_cnt = cnt;
        cnt=0;
        visits = new boolean[n+1][n+1];
 
 		// dltonism 인 경우
        // G를 R로 바꿔주고 수행
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j]=='G'){map[i][j] = 'R'; // G를 R로 바꿔준다.}
            }
        }
 
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visits[i][j]){dfs(i,j); cnt++;}
            }
        }
        int abnormal_cnt = cnt;
        System.out.println(normal_cnt + " " + abnormal_cnt);
    }
 
    public static void dfs(int x, int y){
        visits[x][y] = true;
        char tmp_char = map[x][y]; // R
        for(int i=0; i<4; i++){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
 
            if (new_x<0 || new_y<0 || new_x>n || new_y>n){continue;}
            if (!visits[new_x][new_y] && map[new_x][new_y] == tmp_char){dfs(new_x, new_y);}
        }
    }
}