[알고리즘 PS] 백준 10026번 적록색약 자바 문제풀이

문제

해당 포스팅은 백준의 10026번 적록색약 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

10026번: 적록색약

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS 나 DFS 같은 그래프 탐색에 구현력이 조금 요구되는 문제였다.

 

사실 BFS나 DFS 를 잘 다룰 줄 안다면, 혹은 Silver 1 문제까지 막힘없이 풀 수 있다면 가벼운 문제였다고 생각한다.

 

해결법

 

적록 색약이 구분할 수 있는 색은 빨강과 초록이니 적록색약의 시야에서 빨강과 초록을 하나의 색으로 인식할 수 있도록 하고 정상인은 3가지 색을 모두 다르게 구분해서 연결 요소 찾기를 수행하면 된다.

 

정답 코드

public class Main {

    private static int[] xPos = {1, -1, 0, 0};
    private static int[] yPos = {0, 0, 1, -1};
    private static int n;

    private static boolean[][] visited;
    private static String[][] arr;

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

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

        arr = new String[n][n];


        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                arr[i][j] = s[j];
            }
        }

        int normal = 0;
        int colorBlindness = 0;

        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited[i][j]) { // 방문한 적이 없다면?
                    if(arr[i][j].equals("R")) {
                        visitSingleColor(j, i, "R");
                        normal++;
                    }else if(arr[i][j].equals("G")) {
                        visitSingleColor(j, i, "G");
                        normal++;
                    }else if(arr[i][j].equals("B")) {
                        visitSingleColor(j, i, "B");
                        normal++;
                    }
                }
            }
        }

        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited[i][j]) { // 방문한 적이 없다면?
                    if(arr[i][j].equals("R") || arr[i][j].equals("G")) {
                        visitMultiColor(j, i);
                        colorBlindness++;
                    }else if(arr[i][j].equals("B")) {
                        visitSingleColor(j, i, "B");
                        colorBlindness++;
                    }
                }
            }
        }

        bw.write(normal + " " + colorBlindness);

        bw.flush();
        bw.close();
    }

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

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(Position.isValid(xx, yy)) {
                    if(!visited[yy][xx] && arr[yy][xx].equals(color)) {
                        visited[yy][xx] = true;
                        queue.add(new Position(xx, yy));
                    }
                }
            }
        }
    }

    private static void visitMultiColor(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(x, y));
        visited[y][x] = true;

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(Position.isValid(xx, yy)) {
                    if(!visited[yy][xx] && (arr[yy][xx].equals("R") || arr[yy][xx].equals("G"))) {
                        visited[yy][xx] = true;
                        queue.add(new Position(xx, yy));
                    }
                }
            }
        }
    }

    private static class Position {
        int x;
        int y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        static boolean isValid(int x, int y) {
            return 0 <= x && x < n && 0 <= y && y < n;
        }
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.