[BOJ] 10026: 적록색약 (JAVA)

문제

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

 

여담

골드5치고는 간단하게 BFS 탐색을 수행하면 되는 것이라 쉽게 풀 수 있었다!

 

풀이

같은 색으로 이루어진 구역의 개수를 찾는 것이므로, BFS 또는 DFS 탐색의 호출 횟수를 구하는 것과 같다. 따라서 단순하게 BFS/DFS 탐색을 수행하면 된다.

 

이때, 적록색약인 사람은 빨강과 초록을 구분하지 못하므로 초록(=G)을 빨강(=R)으로 변경한 뒤 탐색을 수행하면 된다.

 

자세한 내용은 아래의 코드를 참고하면 된다.

 

코드

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

public class Main {
    static int N;
    static char[][] pictureO, pictureX; // O: 적록색약 O, X: 적록색약 X
    static boolean[][] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        pictureO = new char[N][N]; // R == G
        pictureX = new char[N][N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                pictureO[i][j] = line.charAt(j);
                pictureX[i][j] = line.charAt(j);
                if (pictureO[i][j] == 'G') pictureO[i][j] = 'R';
            }
        }

        int totalO = 0;
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    totalO++;
                    bfs(i, j, pictureO);
                }
            }
        }

        int totalX = 0;
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    totalX++;
                    bfs(i, j, pictureX);
                }
            }
        }
        System.out.println(totalX + " " + totalO);
    }

    static void bfs(int x, int y, char[][] picture) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + move[i][0];
                int ny = now[1] + move[i][1];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) {
                    continue;
                }

                if (picture[nx][ny] == picture[x][y]) {
                    queue.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

---