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

---

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

---

📌 문제

문제 유형

• 그래프

문제 설명

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.

또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입출력 예시

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

출력

4 3

🔍 문제 풀이

① 입력을 받아 normalGraph와 weaknessGraph 두 개의 2차원 배열 생성

weaknessGraph는 R과 G를 같은 색으로 처리

② BFS를 통해 같은 색으로 연결된 구역 탐색

• 인접한 같은 색을 가진 노드를 모두 방문 처리
• 방문한 칸은 '0'으로 변경하여 다시 방문하지 않도록 함

③ 두 그래프 각각에 대해 BFS를 돌려 영역 개수 카운트 후 출력

💭 놓친 점

놓친 점 1) bfs() 안에서 왜 color 비교를 안했음

• 초기에 작성한 코드:
  • 이 코드는 “아직 방문 안 한 모든 칸” 을 무조건 방문
  • 하지만, “같은 색으로 연결된 영역” 만 세야 하는데,
  • R, G, B 상관없이 모두 방문 → 결국 하나의 큰 덩어리로 인식
    
    

    if (graph[nx][ny] != '0') {
      graph[nx][ny] = '0';
      dq.offer(new int[]{nx, ny});
    }
    

• 수정 후
  • 영역 수를 정확히 셀 수 있음
    
    

    char color = graph[x][y];
    ...
    if (graph[nx][ny] == color) // 같은 색일 때만 연결된 구역으로 보기
    

놓친 점 2) 전역 변수 graph 사용

• graph를 static 전역변수로 사용할 경우, 첫 번째 BFS 탐색에서 값을 변경하면 두 번째 BFS 탐색에 영향을 줌
• 따라서, char[][] graph를 bfs()에 매개변수로 전달해서 각각 처리해야함

놓친 점 3)

• 색약의 경우 R과 G를 구분하지 못하므로, 두 색을 하나로 통일해야 함
• 초반에는 색약 그래프를 따로 만들지 않아서 오류 발생
• 입력 시 R과 G를 모두 같은 문자(R 또는 G)로 통일하여 처리하여 해결

💻 전체 코드

package org.example;

import java.io.*;
import java.util.*;

public class Main {
    static int n;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void bfs(char[][]graph, int x, int y){
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offer(new int[]{x, y});
        char color = graph[x][y]; // 위치 '0' 바꾸기 이전에 존재해야함
        graph[x][y] = '0';


        while(!dq.isEmpty()){
            int[] current = dq.poll();
            int cx = current[0];
            int cy = current[1];

            for(int i=0; i<4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= n ) continue;
                if(graph[nx][ny] == color){
                    graph[nx][ny] = '0';
                    dq.offer(new int[]{nx, ny});
                }

            }
        }

    }

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

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

        char[][] normalGraph = new char[n][n];
        char[][] weaknessGraph = new char[n][n];

        for(int i=0; i<n; i++){
            String input = br.readLine();
            for(int j=0; j<n; j++){
                char c = input.charAt(j);
                normalGraph[i][j] = c;
                weaknessGraph[i][j] = (c=='G') ? 'R' : c; // 놓친 것
            }
        }

        int nomal = 0;
        int weakness = 0;

        // 색약x
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(normalGraph[i][j] != '0'){
                    bfs(normalGraph, i, j);
                    nomal++;
                }
            }
        }

        // 색약o
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(weaknessGraph[i][j] != '0'){
                    bfs(weaknessGraph, i, j);
                    weakness++;
                }
            }
        }

        System.out.println(nomal + " " + weakness);
    }
}