[백준/Java] 10026번 : 적록색약

✏️ 문제 탐색

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

 

NxN 격자판에서 같은 색이 상하좌우로 인접해 있으면 같은 구역으로 세는 문제이다.

단, 적록색약은 R(빨강)과 G(초록)을 같은 색으로 인식한다.

적록색약인 경우, 아닌 경우 각각 구역의 개수를 출력한다.

---

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

위의 예제의 경우,

• 적록색약 O : 총 3구역 인식 (R-G 2, B 1)
• 적록색약 X : 총 4구역 인식 (R 2, B 1, G 1)

 

✏️ 구현 아이디어 

1. 적록색약이 아닌 경우

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

NxN 그리드의 (0, 0) 좌표부터 차례로 탐색을 시작한다.

 

(0, 0)의 색상은 R이다.

이 부분과 상하좌우로 인접한 R들을 찾아서 모두 방문처리한다.

그러면 한 구역을 찾은 것! 구역 개수를 1개 카운트한다.

 

다음으로 탐색할 좌표는 (0, 3)이다. 

(0, 0), (0, 1), (0, 2)은 이전에 R 구역으로 세었으므로 탐색할 필요가 없다.

(0, 3)과 상하좌우로 인접한 B들을 찾아서 모두 방문처리한다.

그러면 또 한 구역을 찾았으므로 구역 개수를 1개 카운트한다.

 

다음으로 탐색할 좌표는 (0, 1)이다.

...

이런 식으로 구역 개수를 세면 된다.

2. 적록색약인 경우

적록색약이 아닌 경우과 같은 방법으로 탐색하되, R과 G를 같은 색상으로 간주해야 한다.

✏️ 알고리즘

• NxN 그리드의 모든 좌표를 탐색해야 함
  -> 그래프 탐색 DFS/BFS를 사용하는 것이 적합해보임
• N의 범위가 100 이하로 그래프 규모가 크지 않은 편이고,
  같은 구역을 구하기 위해 현재 노드와 이어진 모든 노드를 깊이 탐색해야 함
  -> DFS로 결정

✏️ 시간 복잡도

DFS로 모든 노드를 한 번씩만 거치면 되므로 시간 복잡도는 O(N)이다.

노드 수는 최대 10,000개이므로 제한 시간 (1초) 안에 연산 가능하다.

✏️ 코드 설계

1. 입력값을 받음
   1. 적록색약인 경우, 아닌 경우 격자판을 따로 만들 것임
   2. 적록색약이 아니면 그냥 받고
   3. 적록색약일 경우 값이 R이면 G를 입력
   4. 각각 board1, board2로 선언했고 방문 체크 함수도 visited1, visited2로 선언
2. 격자판의 모든 노드 탐색 
   1. 방문하지 않은 노드를 발견하면 dfs 탐색
   2. dfs : 상하좌우 인접 노드가 같은 색이면 계속 재귀호출, 아니면 다음 인접 노드 탐색
   3. 적록색약 격자판의 R의 자리에는 실제로 G가 입력되어있으므로 R과 G가 같은 구역으로 세어질 것이다
3. 각각의 경우 구역의 개수를 출력

✏️ 오답 노트

• board1, board2를 같은 이중 for문 안에 넣어서 틀림
  두 그리드 내부의 색상이 다르기 때문에 dfs를 시작하는 지점도 각자 따로 지정되어야 한다.

for(int i=0; i<N; i++) {
    for (int j = 0; j < N; j++) {
        if (!visited1[i][j]) {
            dfs(board1, visited1, i, j);
            cnt1++;
        }
        if (!visited2[i][j]) {
            dfs(board2, visited2, i, j);
            cnt2++;
        }

    }
}

✏️ 정답 코드

import java.io.*;

public class Main {
    static int N;
    static String[][] board1, board2;
    static boolean[][] visited1, visited2;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

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

        //값 입력받기
        N = Integer.parseInt(br.readLine());

        board1 = new String[N][N];
        board2 = new String[N][N];

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                String val = str.substring(j, j+1);
                board1[i][j] = val;
                //적록색약은 R을 G로 입력
                if(val.equals("R")){
                    board2[i][j] = "G";
                }else board2[i][j] = val;
            }
        }

        visited1 = new boolean[N][N];
        visited2 = new boolean[N][N];

        int cnt1 = 0;
        int cnt2 = 0;

        //적록색약이 아님
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited1[i][j]){
                    dfs(board1, visited1, i, j);
                    cnt1++;
                }

            }
        }

        //적록색약
        for(int i=0; i<N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited2[i][j]) {
                    dfs(board2, visited2, i, j);
                    cnt2++;
                }
            }
        }

        System.out.println(cnt1 + " " + cnt2);

    }
    static void dfs(String[][] board, boolean[][] visited, int x, int y){
        visited[x][y] = true;

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

            if(newX<0 || newX>=N || newY<0 || newY>=N)
                continue;

            //색상이 다르거나 이미 방문했으면 다음 노드 탐색
            if(!board[newX][newY].equals(board[x][y]) || visited[newX][newY])
                continue;

            dfs(board, visited, newX, newY);
        }
    }
}

✏️ Note

• 이제 기본적인 DFS, BFS 문제는 익숙해진듯 하다.
• 알고리즘 하나를 이렇게 자세히 파 본 경험은 처음인데, 템플릿의 도움을 많이 받았다.
• 템플릿 대로 나의 사고흐름을 써내려가보는 것도 많은 도움이 되었고, 나의 풀이와 멘토 해설지를 비교해보며 팁을 얻어가니 두 배로 도움되는 것 같다. 
• 전에 한 번 풀어본 문제라서 그런지 풀이에 할애된 시간이 적었다. 그러나 그 이유뿐만은 아니라고 생각한다. 그래프 문제 풀이 실력이 조금 늘었다.