[BoJ] 백준 10026 - 적록색약 풀이

1. 문제

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

10026번: 적록색약

 

 

 

2. 풀이

깊이 우선 탐색(DFS)의 응용이다. 큰 응용이 아니라 정답 비율이 높은 것 같다.
DFS의 기본적인 내용은 아래의 포스팅을 참고하면 많은 도움이 된다.

https://velog.io/@songyw0517/DFS%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80

DFS란 무엇인가?

 

이 문제를 접근할 때 두 가지의 경우로 접근했다. 

1) 적록색약이 아닌 사람

    적록 색약이 아닌 사람의 경우 R, G, B 각각을 다 다른 문자로 생각하고 구역을 계산하면 된다. 우선 2차원 배열을 만들어 입력 값을 저장해준 후 이차원 배열을 하나씩 탐색하면서 DFS 함수를 실행한다. DFS 함수 안에서 탐색할 때는 상하좌우로 인접해 있는 경우에 같은 구역에 속한다고 했으므로 상하좌우로 움직일 수 있는 dx, dy 배열을 만들고 각각을 더해주면서 탐색한다. 이때 조건은 더했을 때의 값이 배열을 벗어나면 안되고 Main 함수에서 반복 한 바퀴를 돌았을 때 하나의 구역이 카운트 되야 하기 때문에 현재 문자와 다음 탐색할 문자가 같을 경우에만 dfs 함수를 실행한다.

 

2) 적록색약인 사람

    기본적인 로직은 (1)과 같다. 단 적록색약인 사람은 R과 G를 같은 문자로 인식하기 때문에 dfs 함수 안에서 (1) 현재 문자가 R 이고 다음 탐색할 문자가 G인 경우, (2) 현재 문자가 G이고 다음 탐색할 문자가 R인 경우에도 dfs 함수를 실행해야 한다.

 

 

3. 소스코드

package dfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class red_green_weakness {
    static int N;
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[N][N];
        String input;
        int result1 = 0;
        int result2 = 0;

        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[i][j]) {
                    dfs_no(i, j);
                    result1 += 1;
                }
            }
        }

        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[i][j]) {
                    dfs_yes(i, j);
                    result2 += 1;
                }
            }
        }

        bw.write(Integer.toString(result1) + " " + Integer.toString(result2));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs_yes(int x, int y) {
        visited[x][y] = true;

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

            if (xf >= 0 && yf >= 0 && xf < N && yf < N && !visited[xf][yf]) {
                if((map[x][y] == map[xf][yf]) || (map[x][y] == 'R' && map[xf][yf] == 'G') || (map[x][y] == 'G' && map[xf][yf] == 'R'))
                    dfs_yes(xf, yf);
            }
        }
    }

    private static void dfs_no(int x, int y) {
        visited[x][y] = true;

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

            if (xf >= 0 && yf >= 0 && xf < N && yf < N && !visited[xf][yf] && (map[x][y] == map[xf][yf])) {
                dfs_no(xf, yf);
            }
        }
    }
}