[자바] 백준 10026 적록색약

[자바] 백준 으로할지 [백준] 자바로 할지 고민이되는 아침입니다. 

[백준] 자바 보다는 [자바] 백준,,.아님 [java] 백준..보통 이런거 생각하는데 80%정도 시간을 사용하고 나머지 10% 동안 블로그에 글을 씁니다. 

 

이번 문제는 가슴 아픈문제입니다. 

 

더글로리의 재준이가 생각나는군요. 재준이에 대해 더 이야기 하고 싶은데 제가 사실 더글로리를 안봐서 할 이야기가 없네요. 문제나 풀겠습니다.

 

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

10026번: 적록색약

 

<나의 풀이>

 

1<= N <=100 입니다. 가슴이 따듯해집니다. 

 

사실 '아파드 단지 구하기', '섬의 개수 구하기' 와 크게 다를거 없는 문제입니다.

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

2667번: 단지번호붙이기

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

4963번: 섬의 개수

 

보통 여러분은 영역을 구하는 문제에서 DFS를 사용하시나요 BFS를 사용하시나요

 

섬의 개수 처럼 단지 어떤 영역의 수를 카운트 하는 문제에서는 DFS를 사용했고, 다른 어떤 요소를 같이 카운트하는 문제에서는 BFS로 저는 풀었습니다. 

 

본론으로 들어와서 다시 문제를 보자면 역시 영역을 구하는 문제이고, 쪼금 재미있는게 탐색의 기준이 색약인 사람과 아닌 사람 2개입니다.

 

같은 맵을 공유하며 다른 탐색을 표현하는 방법으로는 저번에 '벽 부시고 이동하기' 문제에서 머리 쥐다도록 고민해봐서 쉽게 생각이 났습니다. 

 

3차원 vist 배열을 이용하여 탐색을 2번하면 해결 됩니다.

 

물론 3차원 배열을 사용하지 않고 탐색 자체를 분리하여 2번 실행해도 쉽게 N<=100이라서 구할 수 있을 것 같습니다. 해봐주실래요..?

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static char[][] map;
    static boolean[][][] vist;
    static int[] dx={0,0,1,-1}, dy={1,-1,0,0};
    static class Node{
        int w,h;
        int colorBlindness;
        // 0 = allColor , 1 = colorBlindness
        Node(int h,int w, int colorBlindness){
            this.h = h;
            this.w = w;
            this.colorBlindness = colorBlindness;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        map = new char[n][n];
        vist = new boolean[n][n][2];
        int colorBlindness = 0, color = 0;
        for(int i=0;i<n;i++){
            map[i] = bf.readLine().toCharArray();
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!vist[i][j][0]){
                    color++;
                    BFS(n,i,j,0);
                }
                if(!vist[i][j][1]){
                    colorBlindness++;
                    BFS(n,i,j,1);
                }
            }
            //System.out.println(Arrays.deepToString(vist));
        }
        System.out.println(color+" "+colorBlindness);
    }
    public static void BFS(int n,int h,int w, int colorBlindness){
        // 한번에 덱에 넣고 돌리고 싶은데..메모리 초과날까봐 걱정이요
        Deque<Node> dq = new LinkedList<>();
        vist[h][w][colorBlindness] = true;
        dq.addFirst(new Node(h,w,colorBlindness));
        while (!dq.isEmpty()){
            Node now = dq.pollLast();
            for(int i=0;i<4;i++){
                int nxtH = now.h+dx[i];
                int nxtW = now.w+dy[i];
                if(nxtW<n&&nxtW>=0&&nxtH<n&&nxtH>=0){
                    if(now.colorBlindness==0){
                        if(!vist[nxtH][nxtW][0] && map[now.h][now.w] == map[nxtH][nxtW]){
                            vist[nxtH][nxtW][now.colorBlindness] = true;
                            dq.addFirst(new Node(nxtH,nxtW,0));
                        }
                    }else if(now.colorBlindness==1){
                        if(!vist[nxtH][nxtW][1] && map[now.h][now.w] =='B'){
                            if(map[nxtH][nxtW]=='B'){
                                vist[nxtH][nxtW][now.colorBlindness] = true;
                                dq.addFirst(new Node(nxtH,nxtW,1));
                            }
                        }else if(!vist[nxtH][nxtW][1]){
                            if(map[nxtH][nxtW]=='R' || map[nxtH][nxtW]=='G'){
                                vist[nxtH][nxtW][now.colorBlindness] = true;
                                dq.addFirst(new Node(nxtH,nxtW,1));
                            }
                        }
                    }
                }
            }
        }
    }
}