[백준] 10026번 적록색약 JAVA (자바) 풀이

문제 10026

 

• 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다
• 구역은 같은 색으로 이루어져 있다
• 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급

• 적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다
  
• 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라

 

(예시)

 

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

 

• 적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1)
• 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1)

 

[입력]

 :  첫째 줄에 N (1 ≤ N ≤ 100)

 :  둘째 줄부터 N개 줄에는 그림

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

 

 [출력]

 :   적록색약이 아닌 사람과 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력  

4 3

 

 

 

 [문제접근]

 

• Acount 출력
  
  →  적록색약이 아닐 경우
  →  G / R / B 같은 색이면 방문기록 체크해주고 count
  
  
• Bcount 출력
  
  → 적록색약인 경우
  → G & R / B 같은 색끼리 방문기록 체크해주고 count
  
  
• dfs로 같은 색일 경우의 인접한 노드 모두 확인하고 더이상 접근할 노드가 없다면 dfs 종료 후 구역 count
  
  
• 적록색약이 아닌 경우를 계산하기 위해 아예 두가지 색을 한가지로 만들어버리기
  
  → 아래 코드에서는 레드로 통일

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N;
    static String s;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static char arr[][];
    static boolean visit[][];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N=Integer.parseInt(br.readLine());
        arr= new char[N][N];
        visit= new boolean[N][N];
        int Acount =0;
        int Bcount=0;
      
        for(int i =0; i<N; i++){
            s=br.readLine();
            for(int j=0; j<N; j++){
                arr[i][j]=s.charAt(j);
            }
        }
        
        for(int i =0; i<N; i++){
            for(int j =0; j<N;j++){
                if(!visit[i][j]){
                    dfs(i,j);
                    Acount++;
                }
            }
        }
        
        for(int i=0; i<N;i++){
            for(int j =0; j<N;j++){
                if(arr[i][j]=='G'){
                    arr[i][j]='R';
                }
            }
        }
        
        visit= new boolean[N][N];
        
        for(int i =0; i<N; i++){
            for(int j =0; j<N;j++){
                if(!visit[i][j]){
                    dfs(i,j);
                    Bcount++;
                }
            }
        }
        
        System.out.println(Acount+" "+Bcount);
    }
    
    public static void dfs(int x, int y){
        visit[x][y] = true;
        char color = arr[x][y];
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){
                if(arr[nx][ny]==color){
                    dfs(nx,ny);
                }
            }
        }
    }
}

 

 

 [해설]
     

 :  static int N;  배열판 범위
    static String s;  배열 문자열로 한 줄 씩 받기 
    static int dx[] = {0,0,1,-1};  상하좌우 이동
    static int dy[] = {1,-1,0,0};  상하좌우 이동
    static char arr[][];  배열판
    static boolean visit[][];  방문기록

 :  N=Integer.parseInt(br.readLine());  첫째줄 입력
    arr= new char[N][N];  배열판
    visit= new boolean[N][N];  방문기록 초기화
    int Acount =0;  적록색약 아닌 경우
    int Bcount=0;  적록색약인 경우
 

 :  for(int i =0; i<N; i++){ 
         s=br.readLine();  한 줄의 문자열 가져오기
         for(int j=0; j<N; j++){
              arr[i][j]=s.charAt(j);  문자 하나씩 뜯어보기
         }
    }
      

 :  for(int i =0; i<N; i++){  적록 색약이 아닌 사람의 dfs실행
          for(int j =0; j<N;j++){
                if(!visit[i][j]){  방문기록 없으면 dfs돌리기
                    dfs(i,j);  dfs 실행
                    Acount++;  dfs 끝났으면 한 구역 count
                }
          }
    }
        
 :  for(int i=0; i<N;i++){  
         for(int j =0; j<N;j++){
              if(arr[i][j]=='G'){  적록색약은 G / R 구분이 어렵기 때문에 하나의 색으로 통일
                  arr[i][j]='R';  무조건 R로 통일
              }
         }
    }
        
 :  visit= new boolean[N][N];  적록색약인 사람 때 체크했던 방문기록 다시 초기화
    for(int i =0; i<N; i++){  적록 색약인 사람의 dfs실행
          for(int j =0; j<N;j++){
                if(!visit[i][j]){  방문기록 없으면 dfs돌리기
                    dfs(i,j);  dfs 실행
                    Bcount++; dfs 끝났으면 한 구역 count
                }
          }
    }
        
 :  System.out.println(Acount+" "+Bcount);  결과 출력
    
    
 :  public static void dfs(int x, int y){  dfs 실행
        visit[x][y] = true;  방문기록 체크
        char color = arr[x][y];  컬러도 무슨 색인지 확인 (같은색인지 확인하려고)
        
        for(int i=0;i<4;i++){  
            int nx = x+dx[i];  현위치 x좌표
            int ny = y+dy[i];  현위치 y좌표
            if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){  배열판 범위 안에 있고 방문기록 없으면 실행
                if(arr[nx][ny]==color){  현위치도 같은 색인지 확인하고 진행
                    dfs(nx,ny);  현위치 dfs 반복
                }
            }
        }
    }

 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

10026번: 적록색약