본문 바로가기
Baekjoon/[5] DFS & BFS

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

by Poorm 푸름 2024. 1. 22.

문제 10026 (DFS, BFS)

 

  • 크기가 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
 

 

 

 [문제접근_DFS]

 

  • Acount 출력

    →  적록색약이 아닐 경우
    →  G / R / B 같은 색이면 방문기록 체크해주고 count

  • Bcount 출력

    → 적록색약인 경우
    → G & R / B 같은 색끼리 방문기록 체크해주고 count

  • dfs로 같은 색일 경우의 인접한 노드 모두 확인하고 더이상 접근할 노드가 없다면 dfs 종료 후 구역 count

  • 적록색약이 아닌 경우를 계산하기 위해 아예 두가지 색을 한가지로 만들어버리기

    → 아래 코드에서는 레드로 통일

 

 [DFS 코드]

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 반복
                }
            }
        }
    }

 

 

[문제접근_BFS]

 

  • 정상일 사람과 정상이 아닐 사람의 경우를 구분해서 배열을 바꾸고 bfs를 실행한다

    →  정상인의 경우 원래대로 입력 받고 bfs 실행
    →  정상인이 아닐 경우 배열의 G와 B 같다고 처리 후 bfs 실행

  • bfs메서드 내에서 색 구분

    → 색 체크는 bfs 안에서 한다
    → 같은 색일 경우에만 이동하고 bfs를 빠져나온다
     → count++

 

 

 [BFS 코드]

import java.io.*;
import java.util.*;
public class Main{
    static int dx[]={0,0,1,-1};
    static int dy[]={1,-1,0,0};
    static boolean visit[][];
    static int N;
    static char arr[][];
    
    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];
        for(int i=0;i<N;i++){
            arr[i] = br.readLine().toCharArray();
        }
        
        int normal=0;
        
        for(int i =0; i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]){
                    bfs(i,j);
                    normal++;
                }
            }
        }
    
    
        visit = new boolean[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(arr[i][j]=='G'){
                    arr[i][j]='R';
                }
            }
        }
        
       
        int blind=0;
        for(int i =0; i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]){
                    bfs(i,j);
                    blind ++;
                }
            }
        }
        
        System.out.println(normal);
        System.out.println(blind);
    }
    
    static void bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visit[x][y]=true;
        char color = arr[x][y];
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i =0; i<4;i++){
                int nx = p[0]+dx[i];
                int ny = p[1]+dy[i];
                if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){
                    if(arr[nx][ny]==color){
                        visit[nx][ny]=true;
                        q.add(new int[]{nx,ny});
                    }
                }
            }
        }
    }
}

 

 

 [해설]
     

 :  static int dx[]={0,0,1,-1};  방향이동
    static int dy[]={1,-1,0,0};  방향이동
    static boolean visit[][];  방문기록
    static int N;  입력1
    static char arr[][];  입력배열

     
 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  입력
    arr = new char[N][N];  RGB 배열
       

 :  visit = new boolean[N][N];  평범한 사람일 경우의 기록 초기화

    for(int i=0;i<N;i++){
            arr[i] = br.readLine().toCharArray();  한 줄로 배열 입력 받기
    }
       

 :  int normal=0;  평범한 사람일 경우 카운트
    for(int i =0; i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]){  방문 전이라면 bfs 실행 
                    bfs(i,j);  색 구분은 bfs메서드 안에서 할 것
                    normal++;  같은색 영역 체크 끝났다면 1씩 증가해주기
                }
            }
    }
   

 :  visit = new boolean[N][N];  적록색약인 사람의 경우 기록 초기화
    for(int i=0;i<N;i++){  이번에는 G와 R를 같은 영역으로 만들어 버리기
            for(int j=0;j<N;j++){
                if(arr[i][j]=='G'){  초록색 모두 R로 설정
                    arr[i][j]='R';
                }
            }
    }
        
 :  int blind=0;  적록색약인 사람 카운트 
    for(int i =0; i<N;i++){ 
            for(int j=0;j<N;j++){ 
                if(!visit[i][j]){  방문 전이라면 bfs 실행 
                    bfs(i,j);  색 구분은 bfs메서드 안에서 할 것
                    blind ++;  같은색 영역 체크 끝났다면 1씩 증가해주기
                }
            }
    }
        
 :  System.out.println(normal);  출력1
 :  System.out.println(blind);  출력2


    
 :  static void bfs(int x, int y){  좌표 입력받기
        Queue<int[]> q = new LinkedList<>();  큐선언
        q.add(new int[]{x,y});  큐에 추가하기
        visit[x][y]=true;  방문체크
        char color = arr[x][y];  시작점 좌표 색 체크
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i =0; i<4;i++){  상하좌우 이동 가능
                int nx = p[0]+dx[i];  x좌표
                int ny = p[1]+dy[i];  y좌표
                if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){  범위 안에 있고 방문 전이라면
                    if(arr[nx][ny]==color){  체크한 컬러일 경우에만 이동
                        visit[nx][ny]=true;  방문처리
                        q.add(new int[]{nx,ny});  큐에 추가
                    }
                }
            }
        }
    }


 

 

이제 풀어보러 갈께요 :)



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

 

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

저작자표시

'Baekjoon > [5] DFS & BFS' 카테고리의 다른 글

[백준] 2178번 미로 탐색 JAVA (자바) 풀이  (0) 2024.06.04
[백준] 1707번 이분 그래프 JAVA (자바) 풀이  (1) 2024.01.23
[백준] 2468번 안전 영역 JAVA (자바) 풀이  (1) 2024.01.22
[백준] 2210번 숫자판 점프 JAVA (자바) 풀이  (1) 2024.01.21
[백준] 7576번 토마토 JAVA (자바) 풀이  (0) 2023.09.21

관련글

티스토리툴바