[java 백준] 골드 5/ 10026번 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static class Color{
        int x,y;
        public Color(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public static int n;
    public static int[]dirX={-1,1,0,0};
    public static int[]dirY={0,0,-1,1};
    public static boolean [][]check;
    public static char [][]arr1;
    public static char [][]arr2;
    public static Queue<Color>queue=new LinkedList<Color>();
    public static int ans1,ans2=0;
 
 
    public static void BFS(int i,int j){
 
        check[i][j]=true;
        queue.add(new Color(i,j));
        while(!queue.isEmpty()){
            Color c=queue.poll();
            int xNum=c.x;
            int yNum=c.y;
            for(int k=0;k<4;k++){
                int X=xNum+dirX[k];
                int Y=yNum+dirY[k];
                if(X>=0&&X<n&&Y>=0&&Y<n){
                    //방문했는지 확인 && 같은구역인지 확인
                    if(!check[X][Y]&&arr1[X][Y]==arr1[xNum][yNum]){
                        check[X][Y]=true;
                        queue.add(new Color(X,Y));
 
                    }
                }
            }
        }
 
 
 
 
    }
 
    public static void BFS2(int i,int j){
 
        check[i][j]=true;
        queue.add(new Color(i,j));
        while(!queue.isEmpty()){
            Color c=queue.poll();
            int xNum=c.x;
            int yNum=c.y;
            for(int k=0;k<4;k++){
                int X=xNum+dirX[k];
                int Y=yNum+dirY[k];
                if(X>=0&&X<n&&Y>=0&&Y<n){
                    if(!check[X][Y]&&arr2[X][Y]==arr2[xNum][yNum]){
                        check[X][Y]=true;
                        queue.add(new Color(X,Y));
 
 
                        }
                    }
                }
            }
        }
 
 
 
 
 
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        check=new boolean[n+1][n+1];
        arr1=new char[n+1][n+1];
        arr2=new char[n+1][n+1];
        for(int i=0;i<n;i++){
            String s=sc.next();
            for(int j=0;j<n;j++){
                //문자를 정수형으로
                arr1[i][j]=s.charAt(j);
                check[i][j]=false;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                
                if(arr1[i][j]=='G'){
                    arr2[i][j]='R';
                }
                else{
                    arr2[i][j]=arr1[i][j];
                }
            }
        }
 
 
 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!check[i][j]){
                    BFS(i,j);
                    ans1++;
 
                }
            }
        }
        //check 초기화
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                check[i][j]=false;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!check[i][j]){
                    BFS2(i,j);
                    ans2++;
 
                }
            }
        }
 
        System.out.print(ans1+" "+ans2);
 
 
 
 
 
    }
 
 
 
}
 

 

 

dirX와 dirY 배열을 만들어서 위아래로 탐색할 수 있게 한다. --> 토마토 문제랑 푸는 메커니즘은 거의 똑같다고 보면 된다.

단, 이 문제만의 특징이 두가지 있다.

1. BFS에 인자를 다른 문제들은 0,0부터 넣는데 얘는 for문을 돌리면서 check가 false인 좌표값 i,j를

BFS의 인자로 넣는다. 

그도 그럴게 0,0만 넣어주게 되면 만약 상하좌우의 값을 다 방문한 경우 더 이상 탐색이 불가능하기 때문이다. 

그리고 BFS함수를 빠져나온것 자체가 같은구역인 애들이 상하좌우에 더 없기에 ans를 ++해준다!

 

2. 이건 내가 틀리게 생각한 부분인데 

나는 처음에는 방문했는지 확인하고 arr1[X][Y]!=arr1[xNum] 일때 즉, 다른 구역이면 큐에 값을 추가했는데

큐에 값을 추가하는 것 자체가 같은구역일때만 추가하는거였다. 다른 구역이라면 bfs함수가 종료되어야 했다..ㅋㅋㅋ