백준/10026번/Java - 적록색약 (DFS)

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

10026번: 적록색약

---

https://seungboo.tistory.com/27

백준/2606번/Java - 바이러스 (DFS)

위의 2606번 문제와 마찬가지로 DFS를 활용하여 풀 수 있는 문제이다.

하지만 난이도는 조금 더 높다.

R, G, B의 위치를 char 타입의 이차원 배열에 나타내야 한다.

2606번 문제의 경우, 노드와 간선의 연결관계를 인접리스트에 저장하여, 해당 인접리스트를 for문으로 돌면서 저장된 노드라면 이동을 할 수 있도록 구현하였다.

하지만 이번 문제는 N x N 크기의 이차원 배열 위에서 이동하여야 하므로, 상,하,좌,우 방향으로 모두 이동할 수 있는 지 검사하여야 한다.

따라서 상하좌우 방향의 이동을 나타내는 dx, dy  배열을 활용하였다.

이동방향은 상하좌우 4가지 이므로 0~3까지 반복문을 돌며 각각의 이동방향에 따른 다음 행과 열의 위치를 구하고

해당 위치가 배열을 벗어나지 않았는지, 해당 위치의 색깔이 이동이 가능한 색깔인지 검사할 수 있다.

검사를 모두 통과하면 탐색을 이어가면 된다!

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static boolean[][] visited;
    static char[][] board;
    static char[][] board_blind;

    static int count = 0;
    static int count_blind = 0;
    static int N;
    //행 이동 상하좌우
    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());
        board = new char[N][N];
        board_blind = new char[N][N];
        visited = new boolean[N][N];

        /*
        2차원 배열에 R, G, B를 배치한다.
        i=행 j=열
         */
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<N; j++) {
                char c = s.charAt(j);
                if(c == 'G') {
                    board[i][j] = c;
                    board_blind[i][j] = 'R';
                } else {
                    board[i][j] = c;
                    board_blind[i][j] = c;
                }
            }
        }

        /*
        탐색을 한다. -> 탐색이 종료되면 구역이 1개 나온 것.
        탐색은 (0,0)에서 시작
         */
        for(int x=0; x<N; x++) {
            for(int y=0; y<N; y++) {
                if(!visited[x][y]){
                    dfs(x, y);
                    count++;
                }
            }
        }

        visited = new boolean[N][N]; //방문 배열 초기화.

        for(int x=0; x<N; x++) {
            for(int y=0; y<N; y++) {
                if(!visited[x][y]){
                    dfs_blind(x, y);
                    count_blind++;
                }
            }
        }

        System.out.println(count + " " + count_blind);
    }

    private static void dfs(int x, int y) {
        //이미 방문한 칸이거나 색이 다른 칸이면 방문할 수 없다.
        if(visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(board[nx][ny] == board[x][y]) dfs(nx, ny);

        }


    }
    private static void dfs_blind(int x, int y) {
        if(visited[x][y]){
            return;
        }
        visited[x][y] = true;
        //상단 이동
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(board_blind[nx][ny] == board_blind[x][y]) dfs_blind(nx, ny);

        }
    }
}