[백준] 10026번_적록색약(Java)

문제 풀이

백준의 10026번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

탐색을 통해 같은 색상을 가진 영역을 찾는 문제입니다.

DFS를 활용하여 DFS가 얼마나 수행이 되는지 확인하면 같은 색상의 영역이 몇 개인지 알 수 있을 것입니다. 적록색약이 없는 사람이 보는 영역의 개수를 구하고, ‘G’로 표현된 영역을 ‘R’로 변경한 뒤 다시 DFS를 수행하면 됩니다!

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[1 <= N <= 100\]

• dfs() 함수를 호출하는 이중 for문 N^2 -> 2회 수행 = O(2*N^2)

최악의 경우 약 20,000번의 연산을 수행하기에 시간 내에 문제를 해결할 수 있습니다.

(4) 구현

import java.io.*;

public class Main {
    static int N;
    static char[][] painting;
    static boolean[][] visited;

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

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

        for(int i=0; i<N; i++) {
            painting[i] = br.readLine().toCharArray();
        }

        // 적록색약이 아닌 사람이 봤을 때의 구역의 개수
        int count = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    dfs(new Color(i, j, painting[i][j]));
                    count++;
                }
            }
        }
        int nomal_count = count;
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(painting[i][j] == 'G') painting[i][j] = 'R';
            }
        }

        // 적록색약인 사람이 봤을 때의 구역의 개수
        count = 0;
        visited = new boolean[N][N];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    dfs(new Color(i, j, painting[i][j]));
                    count++;
                }
            }
        }
        
        System.out.println(nomal_count + " " + count);

        br.close();
    }

    static void dfs(Color c) {
        visited[c.x][c.y] = true;

        for(int i=0; i<4; i++) {
            int nx = c.x + dx[i];
            int ny = c.y + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=N) continue;

            if(!visited[nx][ny] && painting[nx][ny] == c.color) {
                dfs(new Color(nx, ny, painting[nx][ny]));
            }
        }
    }

    static class Color {
        int x;
        int y;
        char color;

        public Color(int x, int y, char color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }
    }
}