[BAEKJOON] - 10026번 : 적록색약

10026번 문제

참고 포스팅

• https://nanchachaa.tistory.com/80

📜 알고리즘 접근 방법

해당 문제는 DFS 또는 BFS로 그래프 완전 탐색을 위한 문제입니다.

이번 문제를 풀면서 느낀것은 DFS와 BFS를 선택하는 시점에 어떤 것을 선택해야 하는지에 대한 판단 기준이 부족한것 같다고 생각했습니다.

따라서 해당 포스팅 이후에 두 알고리즘에 대해 명확히 구분하고 판단 기준에 대해 명확히 하는 시간을 가질 예정입니다. - DFS와 BFS 구분

일단, 타 블로그를 참고하여 DFS의 알고리즘으로 구현하였습니다. 접근 방법은 다음과 같습니다.

1. 기본 DFS를 활용하여 범위 갯수를 셉니다.

2. DFS를 통해서 같은 색이 있는 배열 요소까지 방문 배열을 true로 바꿔줍니다.

3. 이 후 적록색약의 시야에서, G를 R로 변경 및 방문 배열을 false로 초기화 해준 뒤 2번 로직과 동일한 방법으로 범위의 갯수를 셉니다.

4. 일반 횟수와 적록색약의 횟수를 출력해줍니다.

👾 구현

import java.io.*;

public class Main {
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int n;
    static String[][] area;
    static boolean[][] visited;

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

        n = Integer.parseInt(br.readLine());

        area = new String[n][n];

        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            area[i] = br.readLine().split("");
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }

        int ancnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = false;
                if (area[i][j].equals("G"))
                    area[i][j] = "R";
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    dfs(i, j);
                    ancnt++;
                }
            }
        }

        br.close();

        System.out.println(cnt + " " + ancnt);
    }

    static void dfs(int c, int r) {
        visited[c][r] = true;
        String color = area[c][r];

        for (int i = 0; i < 4; i++) {
            int col = c + dc[i];
            int row = r + dr[i];

            if (col < 0 || row < 0 || col >= n || row >= n)
                continue;

            if (!visited[col][row] && area[col][row].equals(color)) {
                dfs(col, row);
            }
        }
    }
}