[백준] 10026번 - 적록색약 java

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

 

난이도 : G5

Tag : BFS/DFS

풀이 일자 : 2025-03-06

---

문제 탐색하기

RRRBB
GGBBB

BBBRR
BBRRR
RRRRR

 

N: 그리드의 한 변의 길이 (1 <= N <= 100)

• 그리드의 각 칸은 R(빨강),G(초록),B(파랑)중 하나로 색칠되어 있다.
• 적록색약인 사람은 빨간색과 초록색을 구분하지 못한다.
• 위 그림을 예시로 들면 정상인은 4개의 구역을, 적록색약은 3개의 구역을 보게 된다.

즉 이 문제는 탐색 알고리즘(DFS/BFS)을 사용하여 각 격자를 탐색 후 색깔별로 정상인이 보는 구역의 개수와 적록색약이 보는 구역의 개수를 계산하는 게 핵심입니다.

 

가능한 시간복잡도

먼저 각 구역을 하나하나 탐색해야 하므로 최대 O(100*100) = O(10,000)의 시간복잡도가 걸립니다.

저는 bfs를 두 번 사용하기 때문에 최종적으로 O(N^2) + O(N^2) = O(N^2)의 시간이 소요됩니다.

알고리즘 선택

저는 시간과 메모리 효율을 위해 bfs를 선택하겠습니다.

dfs도 좋은 선택이지만 재귀적으로 호출되기에 bfs(queue 사용)가 더 메모리적 측면에서 낫다고 생각했습니다.

---

코드 설계하기

1. 배열 크기 N을 입력받고, 색깔 정보를 char[][] 배열에 저장합니다.
2. BFS를 사용해 정상인의 구역 개수 탐색합니다.
   • 이때 방문하지 않은 칸부터 탐색을 시작하고, 같은 색이 연결된 모든 칸을 BFS로 탐색합니다.
3. 정상인이 보는 구역의 개수를 구한 후 적록색약 처리를 위해 char 배열을 이중 for문을 돌려 R을 G로 변경합니다.
4. 방문 배열을 초기화하고 다시 BFS 수행합니다.

---

정답코드

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

class Main {
    public static int n;
    public static char[][] grid;
    public static boolean[][] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        grid = new char[n][n];
        visited = new boolean[n][n];

        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<n; j++){
                grid[i][j] = line.charAt(j);
            }
        }

        int normal = bfs();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 'R') grid[i][j] = 'G';
            }
        }

        for (boolean[] row : visited) {
            Arrays.fill(row, false);
        }

        int blindness = bfs();
        
        System.out.println(normal + " " + blindness);
        
    }
    public static int bfs(){
        Queue<int[]> q = new LinkedList<>();
        int dx[] = {0,0,1,-1};
        int dy[] = {-1,1,0,0};
        int area = 0;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(visited[i][j]) continue;
                visited[i][j] = true;
                area++;
                q.add(new int[]{i,j});

                while(!q.isEmpty()){
                    int[] curr = q.poll();
                    int y = curr[0];
                    int x = curr[1];

                    for(int dir=0; dir<4; dir++){
                        int ny = y + dy[dir];
                        int nx = x + dx[dir];

                        if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                        if(visited[ny][nx] || grid[y][x] != grid[ny][nx]) continue;
                        visited[ny][nx] = true;
                        q.add(new int[]{ny, nx});
                    }
                }
            }
        }
        return area;
    }
}