[ 백준 10026 ] 적록색약 (Java) - BFS

---

🔗 문제 링크

10026번: 적록색약

---

💡 문제 풀이 및 해석

1. 평범한 BFS 문제로 본다면, 모든 지점에서 BFS 알고리즘을 구현하여 실행하면 된다.
2. 적록색약과 아닌 상황을 구분해야 하므로, 아래와 같은 과정을 거쳐야 한다.
   3-1. 적록색맹이 아닌 사람에 대해서 BFS로 검사한다.
   3-2. 적록색맹인 사람은 R -> G 로 바꿔서 검사한다.

---

⭐️ 정답 코드 및 설명

import javax.naming.PartialResultException;
import java.awt.image.ImageProducer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {

    static int N;
    static String str;
    static char[][] arr;
    static boolean[][] visit;
    static int[] next_x = {-1, 1, 0, 0};
    static int[] next_y = {0, 0, 1, -1};
    static int rgbAnswer = 0;
    static int noRgbAnswer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader init = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(init.readLine());
        arr = new char[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            str = init.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        int cnt = 0;
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (!visit[y][x]) {
                    BFS(x, y);
                    cnt++;
                }
            }
        }
        System.out.printf("%d ", cnt);

        // 방문 초기화
        cnt = 0;
        visit = new boolean[N][N];

        // 적록색맹은 구별하지 못하는 색
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (arr[y][x] == 'R') {
                    arr[y][x] = 'G';
                }
            }
        }

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (!visit[y][x]) {
                    BFS(x, y);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }

    public static void BFS(int x, int y) {
        LinkedList<int[]> list = new LinkedList<>();
        list.add(new int[]{x, y});
        visit[y][x] = true;

        while (!list.isEmpty()) {
            // 현재 좌표
            int curx = list.getFirst()[0];
            int cury = list.getFirst()[1];
            list.removeFirst(); // 현재위치 추출 완료

            for (int i = 0; i < 4; i++) {
                // 상하 좌우
                int nx = curx + next_x[i];
                int ny = cury + next_y[i];

                // 다음 좌표가 범위안에 있고, 방문하지 않은 곳인가?
                if (nx > -1 && ny > -1 && nx < N && ny < N && !visit[ny][nx]) {
                    // 색이 같다면
                    if (arr[cury][curx] == arr[ny][nx]) {
                        visit[ny][nx] = true; // 방문표시
                        list.add(new int[]{nx, ny}); // 여기서도 찾아보자
                    }
                }
            }
        }
    }
}

---

🤔 문제 후기

처음에는 문제를 풀 때, 초록색을 빨간색으로 바꾼다는 생각보다는 적록색맹인 경우와 아닌 경우로 나누었는데, 생각보다 복잡해져서 다시 문제를 풀면서 아예 맵을 바꿔버리면 굳이 구분을 안해도 되는 것을 알고 바꿨다. 이 부분이 코드를 구현하는 시간을 많이 단축시켜주었다고 생각한다. 그 외의 점은 일반적인 BFS문제 여서 크게 어렵지 않았다.