백준 10026번 ) 적록색약 (java)

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

10026번: 적록색약

 

문제

 

풀이

DFS로 탐색해나가며 주변 영역과 같은지 체크하는 문제이다.

적록색약이 아닌 사람 기준은 일반 DFS 문제로 풀면 되고, 적록색약인 경우 조건을 걸어 빨간색과 초록색을 동일하게 구분하여 영역을 카운트하도록 작성한다.

 

 

코드

import java.io.*;
import java.util.*;

public class BOJ_10026 {

    static int N;
    static char[][] grid;
    static int[][] pictures, patient;
    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));
        N = Integer.parseInt(br.readLine());

        pictures = new int[N][N];
        patient = new int[N][N];
        grid = new char[N][N];

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

        int cnt = 0, paitentCnt = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(pictures[i][j] == 0){
                    cnt++;
                    dfs(i, j, grid[i][j], cnt);
                }

                if(patient[i][j] == 0) {
                    paitentCnt++;
                    patientDFS(i, j, grid[i][j], cnt);
                }
            }
        }
        System.out.println(cnt + " " + paitentCnt);

    }

    static void patientDFS(int y, int x, char color, int cnt) {
        patient[y][x] = cnt;

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

            if(nextX <0 || nextX >=N || nextY<0 || nextY>=N ) continue;
            if(patient[nextY][nextX] != 0) continue;

            char nextColor = grid[nextY][nextX];
            if(nextColor == color) {
                patientDFS(nextY, nextX, nextColor, cnt);
            } else{
                if((color == 'R' && nextColor == 'G') || (color=='G' && nextColor =='R')) {
                    patientDFS(nextY, nextX, nextColor, cnt);
                }
            }
        }

    }

    static void dfs(int y, int x, char color, int cnt) {
        pictures[y][x] = cnt;

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

            if(nextX <0 || nextX >=N || nextY<0 || nextY>=N ) continue;
            if(pictures[nextY][nextX] != 0) continue;

            char nextColor = grid[nextY][nextX];
            if(nextColor == color) {
                dfs(nextY, nextX, nextColor, cnt);
            }
        }

    }
        
}