[문제 풀이] 백준 10026번 적록색약 JAVA

문제

  문제접근 방법   

해당 문제는 N이주 어지고 N x N 크기의 구역에 각각 R(red), G(green), B(blue)가 입력되었을 때 색약이 아닌 사람과 적록색약인 사람이 구역을 전체 몇 개로 보는지를 출력하는 문제이다. 예를 들어 색약이 아닌 사람은 4개로 보지만 적록 색약인 사람은 R과 G가 같은 색 즉 같은 구역으로 보이기 때문에 이보다 적은 구역을 확인할 수도 있는 것이다.

문제를 처음읽고 DFS로 문제를 해결해야겠다는 생각이 들었다. 색약인 사람과 아닌 사람을 각각 다른 dfs를 설정해 탐색하고

색약의 경우 R,G일때만 같은 구역으로 묶는 처리를 해주면 해결되겠다 생각해 아래와 같이 코드를 작성하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static char color[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int colorblind=0;
        int notColorblind=0;
        visited=new boolean[n][n];
        color=new char[n][n];
        
        for(int i=0;i<n;i++){
            String str=s.next();
            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]){
                   dfs(i,j,color[i][j]);
                   notColorblind++;
               }
            }
        }
        visited=new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
               if(!visited[i][j]){
                   dfs2(i,j,color[i][j]);
                   colorblind++;
               }
            }
        }
        System.out.println(notColorblind+" "+colorblind);
    }
    
    public static void dfs(int x,int y,char start){
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        visited[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<visited.length&&ny<visited[0].length){
                if(!visited[nx][ny]&&start==color[nx][ny]){
                    dfs(nx,ny,start);
                }
            }
        }
    }
    
    public static void dfs2(int x,int y,char start){
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        visited[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<visited.length&&ny<visited[0].length&&!visited[nx][ny]){
                if(start==color[nx][ny]){
                    dfs2(nx,ny,start);
                }
                else if((start=='R'&&color[nx][ny]=='G')||(start=='G'&&color[nx][ny]=='R')){
                    dfs2(nx,ny,start);
                }
            }
        }
    }
    
}

위에서 설명한데로 코드를 작성하였더니 손쉽게 맞았다는 결과를 받을 수 있었다.

먼저 색약인 경우는 영역의 수를 카운트하는데 여기서 핵심은 매개변수로 시작점의 색깔을 넘겨주는 것이다. 

그래서 시작점의 색깔 기준으로 같으면 같은 영역이므로 탐색을 이어가고 아니라면 더 이상 탐색하지 않은 것이다.

적록 색약인 사람이 구역을 보고 영역이 몇 개인지 카운트할 때는 하나의 처리가 더 필요한데 바로 R과 G를 같은 영역으로 취급하는 것이다. 그러니까 시작점의 색깔이 R이라고 할 때 상하좌우 중에 R이나 G가 있다면 이동해 영역으로 치고 탐색을 이어가는 것이다.

위의 코드에서는  if elseif 문으로 해당 문제를 해결하였다. 처음 if문에서는  start(시작점의 색깔)과 color[nx][ny](현재 색깔)이 같다면 탐색을 이어간다. 예를 들어 R==R, G==G, B==B이다. if문에서 조건이 만족하지 않는다면 else if문으로 넘어가게 되는데

시작값이 R이고 현재값이 G이거나 시작값이 G이고 현재값이 R인경우는 탐색을 이어간다. 이 한 문장을 통해 적록색약이 보는 시약의 영역 구분을 구현한 것이다.

여기서  else로 처리하면 되지 않나? 라는 생각을 할 수도 있다. 아쉽게도 불가능하다. else로 처리할 경우 같지 않으면 탐색을 이어간다는 의미이기 때문에 아마도 모든 영역이 하나로 취급되어 무조건 1이 출력될 것이라고 생각된다.

 

  마무리  

해당 문제는 적록색약과 색약이 아닌 사람의 시야에서 보는 영역구분에 관한 문제였다. 골드 난이도 치고는 아이디어만 떠올랐다면쉽게 접근 가능했을 것이라고 생각되고 개인적으로 조건을 통해서 분기를 나누어 처리하는 부분이 인상적이고 재미있었다.

  추가 코드 분석 및 풀이  

추가적으로 다른 분들이 풀어 놓은 코드 풀이도 읽어보았다는데

dfs를 활용해 문제를 해결한다는 부분을 같았고 세부적인 내용들이 달랐다. 예를 들어 본인은 색약과 색약이 아닌 사람이 보는 영역의 차이를 dfs를 2개 활용해 구현하였지만 color의 R을 G로 바꾸어서 탐색하다던가 아예 bfs를 활용한 경우도 있었다.

하지만 큰 틀의 차이는 거의 없었기 때문에 추가적인 코드 분석과 풀이는 작성하지 않겠다.