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

🔗 문제 링크

BOJ 10026번: 적록색약

10026번: 적록색약

 

📝 풀이 과정

반복문을 통해 순차적으로 접근하여 만약 방문하지 않은 점일때, 주변에 같은 색 영역이 존재하는 경우 방문처리를 해주면 되는 DFS, BFS 문제이다.

 

이번에는 DFS로 풀어보기로 했다.

이 문제에는 색약이 아닌 경우와 색약인 경우의 2가지의 탐색이 필요하다. 색약이 아닌 경우를 먼저 탐색하고 이후 색약인 경우를 탐색하기로 했다.

 

반복문을 돌며 해당 칸을 방문하지 않은 경우,dfs 메소드를 통해 해당 칸의 y값과 x값, 일치해야 하는 색(char)을 전달하고, visit배열의 주소값을 전달하여 갱신되도록 하였다. 한 구역이 확보되었기 때문에 ans++ 해주었다.

색약이 아닌 경우(k = 0)의 탐색을 시작하고 방문한 칸은 더 이상 방문하지 않기 때문에 'G' -> 'R'로 바꾸어주어도 문제가 발생하지 않는다.

 

따라서, 다음 색약인 경우(k = 1)의 탐색에서 간단하게 'G'와 'R'을 처리할 수 있게 된다.

 

💻 코드

import java.util.Scanner;

public class Main {
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int N;
    static char[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        map = new char[N][N];
        for (int i = 0; i < N; i++)
            map[i] = sc.next().toCharArray();

        int[] ans = {0, 0};
        boolean[][][] visit = new boolean[2][N][N];

        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visit[k][i][j]) {
                        dfs(i, j, visit[k], map[i][j]);
                        ans[k]++;
                    }
                    if (map[i][j] == 'G')
                        map[i][j] = 'R';
                }
            }
        }
        System.out.println(ans[0] + " " + ans[1]);

    }

    static void dfs(int y, int x, boolean[][] visit, char ch) {
        visit[y][x] = true;

        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N || visit[ny][nx] || map[ny][nx] != ch)
                continue;
            dfs(ny, nx, visit, ch);
        }
    }


}

 

📊 제출 결과