[JAVA] 백준 - 10026 : 적록색약

문제 링크

10026번: 적록색약

 

 

풀이 ) DFS

  적록색약이 아닌 사람은 R, G, B를 각각 따로 / 적록색약인 사람은 R과G를 구분하지 않고, B만 따로 봐주면 된다.

  각각 다르게 DFS를 구현할 수 있지만 같은 메서드에 대해서 flag를 다르게 넘겨주어 다음 칸이 유효한지 확인하는 부분만 다르게 구현했다.

 

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

public class Main {
    static int n;
    static char[][] board;
    static boolean[][] visited;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        board = new char[n][];
        for(int i = 0; i < n; ++i)
            board[i] = br.readLine().toCharArray();

        visited = new boolean[n][n];
        int ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], false);
                    ans++;
                }
            }
        }
        sb.append(ans).append(' ');

        visited = new boolean[n][n];
        ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], true);
                    ans++;
                }
            }
        }
        sb.append(ans);
        System.out.println(sb);
    }

    static void dfs(int x, int y, char c, boolean flag){
        visited[x][y] = true;
        for(int dir = 0; dir < 4; ++dir){
            int nx = x+dx[dir], ny = y+dy[dir];
            if(!isIn(nx, ny, c, flag) || visited[nx][ny])
                continue;
            dfs(nx, ny, c, flag);
        }
    }

    static boolean isIn(int x, int y, char c, boolean flag){
        if(flag){
            if(c == 'B')
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == 'B';
            else
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] != 'B';
        }
        return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == c;
    }
}

 

주의 )

- visited와 ans의 초기화