[백준 10026번 / Java] 적록색약 - DFS/BFS

문제 링크

Gold 5

 

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

10026번: 적록색약

 

 

 

 

풀이

필자는 BFS를 이용해 풀었으며 실버 DP문제들 보다 난이도가 쉬운 것 같다.

 

처음에는, BFS 메서드를 통해 한 번 완전탐색을 끝낸 후 바로 결과를 도출시키려고 했고, 실패했다.

이유는 모든 결과를 고려하지 않아서 인 것 같다. 어떤 경우였냐면

//bfs메서드의 파라미터로 color을 받아 RGBCheck배열 체크
switch(color) {
    case 'R': RGBCheck[0]++;
        break;
    case 'G': RGBCheck[1]++;
        break;
    case 'B': RGBCheck[2]++;
        break;
}

int[] RGBCheck = new int[3];

int answer1 = RGBCheck[0] + RGBCheck[1] + RGBCheck[2];
int answer2 = Math.max(RGBCheck[0], RGBCheck[1]) + RGBCheck[2]; //문제 발생

System.out.println(answer1 + " " + answer2);

위처럼 결과 도출 과정에서, RED와 GREEN중 많이 나온쪽만 계산해서 도출했으며, 이렇게 되면 RED와 GREEN을 다른 색으로 인식시켜(?) 예외 케이스가 발생한다. 즉 하나의 색으로 판별하는 것이 아니게 된다.

 

나의 경우, 위 상황만 고려하여 재설계하였고 아래와 같은 과정으로 풀어냈다

1. 필요한 배열 생성

2. input 시 적록색약을 위한 배열을 따로 생성하였기 때문에, 한번에 insert

3. 일반 사람의 경우 확인

4. 초기화

5. 적록색약 확인

6. output

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int[] xArr = {-1, 1, 0, 0};
    static int[] yArr = {0, 0, -1, 1};
    static char[][] RGB;
    static char[][] RGB2;
    static boolean[][] visited;
    static int[] RGBCheck = new int[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        RGB = new char[N][N];
        RGB2 = new char[N][N];
        visited = new boolean[N][N];

        //적록색약을 위한 RGB2 생성. insert 시 한번에
        for (int i = 0; i < N; i ++) {
            String color = br.readLine();
            for (int j = 0; j < N; j ++) {
                RGB[i][j] = color.charAt(j);

                if(color.charAt(j) == 'G') {
                    RGB2[i][j] = 'R';
                }
                else RGB2[i][j] = color.charAt(j);
            }
        }

        //적록색약이 아닌 사람의 bfs
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++) {
                if(!visited[i][j]) bfs(RGB[i][j], i, j, "RGB");
            }
        }
        
        int answer1 = RGBCheck[0] + RGBCheck[1] + RGBCheck[2];
        
        //적록색약을 위한 초기화
        RGBCheck = new int[3];
        visited = new boolean[N][N];

        //적록색약의 bfs
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++) {
                if(!visited[i][j]) bfs(RGB2[i][j], i, j, "RGB2");
            }
        }

        int answer2 = RGBCheck[0] + RGBCheck[1] + RGBCheck[2];
        System.out.println(answer1 + " " + answer2);

    }

    private static void bfs(char color, int y, int x, String tmp) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{y, x});
        visited[y][x] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i ++) {
                int[] current = queue.poll();
                x = current[1];
                y = current[0];

                for (int j = 0; j < 4; j ++) {
                    int newX = x + xArr[j];
                    int newY = y + yArr[j];

                    if(newY < 0 || newY >= N || newX < 0 || newX >= N || visited[newY][newX]) continue;
                    if(tmp.equals("RGB")) {
                        if(RGB[newY][newX] == RGB[y][x]) {
                            queue.add(new int[]{newY, newX});
                            visited[newY][newX] = true;
                        }
                    }
                    else {
                        if(RGB2[newY][newX] == RGB2[y][x]) {
                            queue.add(new int[]{newY, newX});
                            visited[newY][newX] = true;
                        }
                    }
                }
            }
        }
        
        //처음 들어왔던 color을 활용하여 어떤 color을 탐색했는지 식별
        switch(color) {
            case 'R': RGBCheck[0]++;
                break;
            case 'G': RGBCheck[1]++;
                break;
            case 'B': RGBCheck[2]++;
                break;
        }
    }
}