[백준 / Java] 10026: 적록색약 (BFS)

난이도: Gold 5

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

 

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

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

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

---

 

구역을 나누고 개수를 구할 때에는 BFS 알고리즘을 사용하면 된다.

 

 

주어진 배열 중에 같은 영어가 써있는 곳은 같은 구역으로 취급하고 구역을 나눈다.

적록색약이 아닐 때는 빨간색 구역 2개, 파란색 구역 1개, 초록색 구역 1개로 총 4개이다.

코드는 다음과 같다.

 

    int areaCount = 0;  // 적록색약이 아닌 사람이 봤을 때의 구역의 개수

   

    // 모든 칸을 탐색

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            // 해당 칸을 방문하지 않았거나, 해당 칸이 빨간색이라면

            if (!visited[i][j] && grid[i][j] == 'R') {

                areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가

                bfs(i, j, 'R'); // 이 구역에 해당하는 빨간색 칸을 모두 방문 체크하는 bfs 수행

            }

            // 해당 칸을 방문하지 않았거나, 해당 칸이 초록색이라면

            else if (!visited[i][j] && grid[i][j] == 'G') {

                areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가

                bfs(i, j, 'G'); // 이 구역에 해당하는 초록색 칸을 모두 방문 체크하는 bfs 수행

            }

            // 해당 칸을 방문하지 않았거나, 해당 칸이 파란색이라면

            else if (!visited[i][j] && grid[i][j] == 'B') {

                areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가

                bfs(i, j, 'B'); // 이 구역에 해당하는 파란색 칸을 모두 방문 체크하는 bfs 수행

            }

        }

    }

 

 

방문하지 않은 칸은 새로운 구역이라는 뜻이므로, areaCount(적록색약이 아닐 때의 구역 개수)를 1 증가시킨다.

bfs 메서드에서 인자로 넘어간 색깔만 탐색한다.

이 areaCount는 최종 출력할 값이다. 

 

이제 적록색약일 때의 구역 개수를 구해야 한다.

적록색약일 때에는 빨간색과 초록색을 구분할 필요가 없으므로,

G(초록색)가 적혀있는 칸을 모두 R(빨간색)으로 바꾼다.

 

    // 모든 칸을 탐색

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            // 모든 초록색 칸을 빨간색 칸으로 바꾸기 => 빨간색과 초록색을 같은 색으로 취급

            if (grid[i][j] == 'G') {

                grid[i][j] = 'R';

            }

        }

    }

 

 

 

G(초록색)을 모두 R(빨간색)으로 바꾼 후 구역을 다시 나눈다.

그런데 구역을 새로 나눠야 하므로 구역을 나누기 전에 방문 배열을 초기화해야 한다.

적록색약일 때는 빨간색 구역 2개, 파란색 구역 1개으로 총 3개이다.

코드는 다음과 같다.

 

    visited = new boolean[N][N];    // 구역을 다시 나눠야 하므로 방문 배열 초기화

    int areaCountOfRedGreen = 0;    // 적록색약인 사람이 봤을 때의 구역의 수

   

    // 모든 칸을 탐색

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            // 해당 칸을 방문하지 않았거나, 해당 칸이 빨간색이라면

            if (!visited[i][j] && grid[i][j] == 'R') {

                areaCountOfRedGreen++;  // 적록색약인 사람이 봤을 때의 구역 개수 1 증가

                bfs(i, j, 'R'); // 이 구역에 해당하는 빨간색 칸을 모두 방문 체크하는 bfs 수행

            }

            // 해당 칸을 방문하지 않았거나, 해당 칸이 파란색이라면

            else if (!visited[i][j] && grid[i][j] == 'B'){

                areaCountOfRedGreen++;  // 적록색약인 사람이 봤을 때의 구역 개수 1 증가

                bfs(i, j, 'B'); // 이 구역에 해당하는 파란색 칸을 모두 방문 체크하는 bfs 수행

            }

        }

    }

 

 

방문하지 않은 칸은 새로운 구역이라는 뜻이므로, areaCountOfRedGreen(적록색일 때의 구역 개수)를 1 증가시킨다.

G(초록색)을 모두 R(빨간색)으로 바꿨으므로, 더 이상 G일 때는 구할 필요가 없다.

bfs 메서드에서 인자로 넘어간 색깔만 탐색한다.

이 areaCountOfRedGreen은 최종 출력할 값이다. 

 

이제 bfs 메서드의 구현을 보자.

 

    public static void bfs(int x, int y, char color) {

        Queue<Point> queue = new LinkedList<>();    // bfs 수행을 위한 큐

        queue.add(new Point(x, y));     // 큐에 시작 칸 삽입

        visited[x][y] = true;   // 매개변수 color와 같은 색인 시작 칸을 방문 체크

       

        // 큐가 빌 때까지 반복

        while (!queue.isEmpty()) {

            Point now = queue.poll();   // 큐에서 현재 칸 뽑기

           

            // 현재 칸 기준 상, 하, 좌, 우 탐색

            for (int i = 0; i < 4; i++) {

                int nx = now.x + dx[i];     // 인접 칸의 x좌표

                int ny = now.y + dy[i];     // 인접 칸의 y좌표

               

                // 인접 칸의 x좌표, y좌표가 유효 인덱스 범위를 벗어난다면 건너뛰기

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) {

                    continue;

                }

               

                // 인접 칸을 이미 방문했거나,

                // 인접 칸의 색이 매개변수 color의 색과 다르다면 건너뛰기

                if (visited[nx][ny] || grid[nx][ny] != color) {

                    continue;

                }

               

                queue.add(new Point(nx, ny));   // 인접 칸을 큐에 삽입

                visited[nx][ny] = true;     // 매개변수의 color와 같은 색인 인접 칸을 방문 체크

            }

        }

    }

 

 

2차원 배열 BFS 알고리즘의 흔한 로직이다.

매개 변수로 넘어온 색깔과 같을 때만 모두 방문 체크를 해주면 된다. 

 

 

자, 이제 전체 코드를 보자. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class P10026_적록색약 {
    static int N;                        // 그리드의 가로, 세로 크기
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static char[][] grid;                // 2차원 그리드 배열
    static boolean[][] visited;            // 2차원 방문 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        grid = new char[N][N];
        visited = new boolean[N][N];
        
        // 2차원 그리드 배열 초기화
        for (int i = 0; i < N; i++) {
            String line = br.readLine();    // 한 줄 받아오기
            for (int j = 0; j < N; j++) {
                // 'R': 빨간색, 'G': 초록색, 'B': 파란색
                grid[i][j] = line.charAt(j);
            }
        }
        
        int areaCount = 0;    // 적록색약이 아닌 사람이 봤을 때의 구역의 개수
        
        // 모든 칸을 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 해당 칸을 방문하지 않았거나, 해당 칸이 빨간색이라면
                if (!visited[i][j] && grid[i][j] == 'R') {
                    areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가
                    bfs(i, j, 'R');    // 이 구역에 해당하는 빨간색 칸을 모두 방문 체크하는 bfs 수행
                }
                // 해당 칸을 방문하지 않았거나, 해당 칸이 초록색이라면
                else if (!visited[i][j] && grid[i][j] == 'G') {
                    areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가
                    bfs(i, j, 'G');    // 이 구역에 해당하는 초록색 칸을 모두 방문 체크하는 bfs 수행
                } 
                // 해당 칸을 방문하지 않았거나, 해당 칸이 파란색이라면
                else if (!visited[i][j] && grid[i][j] == 'B') {
                    areaCount++;    // 적록색약이 아닌 사람이 봤을 때의 구역 개수 1 증가
                    bfs(i, j, 'B');    // 이 구역에 해당하는 파란색 칸을 모두 방문 체크하는 bfs 수행
                }
            }
        }
        
        // 모든 칸을 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 모든 초록색 칸을 빨간색 칸으로 바꾸기 => 빨간색과 초록색을 같은 색으로 취급
                if (grid[i][j] == 'G') {
                    grid[i][j] = 'R';
                }
            }
        }
        
        visited = new boolean[N][N];    // 구역을 다시 나눠야 하므로 방문 배열 초기화
        int areaCountOfRedGreen = 0;    // 적록색약인 사람이 봤을 때의 구역의 수
        
        // 모든 칸을 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 해당 칸을 방문하지 않았거나, 해당 칸이 빨간색이라면
                if (!visited[i][j] && grid[i][j] == 'R') {
                    areaCountOfRedGreen++;    // 적록색약인 사람이 봤을 때의 구역 개수 1 증가
                    bfs(i, j, 'R');    // 이 구역에 해당하는 빨간색 칸을 모두 방문 체크하는 bfs 수행
                } 
                // 해당 칸을 방문하지 않았거나, 해당 칸이 파란색이라면
                else if (!visited[i][j] && grid[i][j] == 'B'){
                    areaCountOfRedGreen++;    // 적록색약인 사람이 봤을 때의 구역 개수 1 증가
                    bfs(i, j, 'B');    // 이 구역에 해당하는 파란색 칸을 모두 방문 체크하는 bfs 수행
                }
            }
        }
        
        // 적록색약이 아닌 사람이 봤을 때의 구역의 개수, 적록색약인 사람이 봤을 때의 구역의 개수 출력
        System.out.println(areaCount + " " + areaCountOfRedGreen);
    }
    
    public static void bfs(int x, int y, char color) {
        Queue<Point> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        queue.add(new Point(x, y));        // 큐에 시작 칸 삽입
        visited[x][y] = true;    // 매개변수 color와 같은 색인 시작 칸을 방문 체크
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Point now = queue.poll();    // 큐에서 현재 칸 뽑기
            
            // 현재 칸 기준 상, 하, 좌, 우 탐색
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];        // 인접 칸의 x좌표
                int ny = now.y + dy[i];        // 인접 칸의 y좌표
                
                // 인접 칸의 x좌표, y좌표가 유효 인덱스 범위를 벗어난다면 건너뛰기
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
                    continue;
                }
                
                // 인접 칸을 이미 방문했거나,
                // 인접 칸의 색이 매개변수 color의 색과 다르다면 건너뛰기
                if (visited[nx][ny] || grid[nx][ny] != color) {
                    continue;
                }
                
                queue.add(new Point(nx, ny));    // 인접 칸을 큐에 삽입
                visited[nx][ny] = true;        // 매개변수의 color와 같은 색인 인접 칸을 방문 체크
            }
        }
    }
    
    static class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}