[Baekjoon] 10026번: 적록색약 - Java

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

10026번: 적록색약

문제 설명

기본적인 DFS 문제이다. RGB 픽셀로 이루어진 입력이 주어지고 일반 사람과 적록색약이 볼 수 있는 구역의 수를 구하면 된다.

풀이 방법

일반인과 적록색약이 보는 그림을 구분하기 위해 먼저 두 개의 배열을 준비하고 입력받았다. 적록색약의 그림은 G를 R로 대신 입력하면 된다(또는 그 반대).

for (int x = 0; x < N; x++) {
    char[] pixels = br.readLine().toCharArray();
    for (int y = 0; y < N; y++) {
        pictureForNoamrl[x][y] = pixels[y];
        pictureForAbnormal[x][y] = pixels[y] == 'G' ? 'R' : pixels[y];
    }
}

이 문제는 구역을 구분하기만 하면 되기 때문에 DFS로 방문할 수 있는 모든 노드를 탐색하기만 하면 된다. 즉, 같은 색으로 이어진 구역을 계속 탐색하다가 다른 색이 나오면 돌아가면 된다.

private static void dfs(int x, int y, char[][] picture) {
    isVisited[x][y] = true;
    char currentPixel = picture[x][y];

    // 상하좌우로 움직이며 방문할 수 있는 픽셀 탐색
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX < 0 || nextY < 0 || nextX > N || nextY > N)
            continue;

        if (!isVisited[nextX][nextY] && picture[nextX][nextY] == currentPixel)
            dfs(nextX, nextY, picture);
    }
}

그리고 함수가 종료되면 카운트를 증가시키면 된다.

for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++) {
        if (!isVisited[x][y]) {
            dfs(x, y, pictureForNoamrl);
            count++;
        }
    }
}

 

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ10026 {
    static int normal = 0;
    static int abnormal = 0;
    static int N;
    static char[][] pictureForNoamrl;
    static char[][] pictureForAbnormal;
    static boolean[][] isVisited;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, 1, -1, 0};

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

            pictureForNoamrl = new char[N + 1][N + 1];
            pictureForAbnormal = new char[N + 1][N + 1];
            isVisited = new boolean[N + 1][N + 1];

            for (int x = 0; x < N; x++) {
                char[] pixels = br.readLine().toCharArray();
                for (int y = 0; y < N; y++) {
                    pictureForNoamrl[x][y] = pixels[y];
                    pictureForAbnormal[x][y] = pixels[y] == 'G' ? 'R' : pixels[y];
                }
            }

            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    if (!isVisited[x][y]) {
                        dfs(x, y, pictureForNoamrl);
                        normal++;
                    }
                }
            }

            isVisited = new boolean[N + 1][N + 1]; // 방문 기록 초기화

            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    if (!isVisited[x][y]) {
                        dfs(x, y, pictureForAbnormal);
                        abnormal++;
                    }
                }
            }

            System.out.print(normal + " " + abnormal);
        }
    }

    private static void dfs(int x, int y, char[][] picture) {
        isVisited[x][y] = true;
        char currentPixel = picture[x][y];

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextY < 0 || nextX > N || nextY > N)
                continue;

            if (!isVisited[nextX][nextY] && picture[nextX][nextY] == currentPixel)
                dfs(nextX, nextY, picture);
        }
    }
}