BOJ10026 / 적록색약

문제 요약

NxN 그리드의 각 칸이 RGB로 칠해진 그림이 같은 색으로 이루어진 몇 개의 구역으로 나뉘어 있다.

같은 색상이 상하좌우로 인접해 있는 경우 같은 구역에 속한다.

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

위 그림을 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개 (R 2, B 1, G 1), 적록색약인 사람이 봤을 때는 총 3개 구역을 볼 수 있다.(R-G 2, B 1)

그림이 입력으로 주어질 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하라.

 

입력

첫째 줄에 N이 주어진다. (1 <= N <= 100)

둘째 줄부터 N+1줄 까지 그림이 주어진다.

 

 

출력

적록색약이 아닌 사람이 봤을 때의 구역 수와 적록색약인 사람이 봤을 때의 구역 수를 공백으로 구분해 출력한다.

 

예제 입력

5

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

 

예제 출력

4 3

 

// https://www.acmicpc.net/problem/10026
// 20.8.14. ventania1680
// BFS
package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ10026 {
    static boolean[][] visited;
    static Queue<Integer> q;
    static char[][] img;
    static int n;
    final static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    static void BFS(int i, int j) {
        q.offer(i * 1000 + j);
        visited[i][j] = true;
        while(!q.isEmpty()) {
            int y = q.poll();
            int x = y % 1000;
            y /= 1000;
            // 상하좌우
            for (int k = 0; k < 4; k++) {
                y += dir[k][0];
                x += dir[k][1];
                // 유효한 좌표인지 검사
                if (y >= 0 && y < n && x >= 0 && x < n) {
                    // 방문한 적 없고 같은 색일 경우
                    if (!visited[y][x] && img[i][j] == img[y][x]) {
                        q.offer(y * 1000 + x);
                        visited[y][x] = true;
                    }
                }
                y -= dir[k][0];
                x -= dir[k][1];
            }
        }
    }

    public static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        img = new char[n][n];
        for (int i = 0; i < n; i++)
            img[i] = br.readLine().toCharArray();

        visited = new boolean[n][n];
        for (int i = 0; i < n; i++)
            Arrays.fill(visited[i], false);
        q = new LinkedList<>();
        int zone1 = 0, zone2 = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 방문한 적 없는 좌표의 경우 BFS로 탐색
                if (!visited[i][j]) {
                    zone1++;
                    BFS(i, j);
                }
            }
        }
        // 적록색약
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (img[i][j] == 'G')
                    img[i][j] = 'R';
            }
            // visited 배열 초기화
            Arrays.fill(visited[i], false);
        }
        // 큐 초기화
        q.clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    zone2++;
                    BFS(i, j);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(zone1 + " " + zone2);
        System.out.print(sb);
    }
}

 

문제 풀이

DFS, BFS 둘 중 어느 것을 사용하더라도 풀 수 있는 문제다. 위 소스코드는 BFS를 사용했다.

img 배열에 그림(RGB)을 저장했고, visited 배열에 해당 좌표 방문 여부를 저장했다.

dir 배열은 상하좌우 방향을 의미한다. 코드 압축을 위해서 사용했다.

 

2중 for문으로 왼쪽 위(0, 0)에서부터 img 배열을 참조하면서 방문하지 않은 좌표에 도착하면 카운트하고 해당 점에서 BFS를 시작한다.

BFS는 현재 위치에서 상하좌우를 참조하여 방문한 적이 없고 현재 위치와 같은 색이라면 해당 좌표를 큐에 넣는다.

적록색약의 경우는 img 배열의 모든 'G'를 'R'로 바꾸어 위 과정을 반복한다.

 

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

10026번: 적록색약

https://github.com/ventania1680/algorithm/blob/master/Algorithm/src/BOJ/BOJ10026.java

ventania1680/algorithm