[Java] BOJ 10026 적록색약

문제

문제 링크 https://www.acmicpc.net/problem/11723

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
```
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
```
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

아이디어

우선 입력부터 적록색약인 사람과 아닌사람을 구분해서 따로 배열에 저장했다.
적록색약이 아닌 사람들은 모든 색을 볼 수 있으므로 입력받는 그대로를 저장하고, 적록색약인 사람들은 R과 G를 구분해서 보지 못하니 G를 입력받을 때마다 R로 바꿔서 저장했다.
그리고 각각의 배열에 대한 방문처리를 저장할 boolean 2차원 배열을 따로 만들고 BFS를 돌렸다.
모든 노드를 돌면서 우선 적록색약이 아닌 사람들의 배열에서 방문하지 않은 노드를 만났을 때, 해당 좌표값을 Queue에 넣고 좌표값에 해당하는 색을 따로 저장해준다.
그리고 상하좌우를 이동하면서 배열을 벗어나지 않으면서 방문하지 않았고 처음 입력들어온 좌표의 색과 같을 경우, 이동한 좌표값을 방문처리하고 Queue에 넣어준다.
그리고 Queue에 아무런 값도 없을 경우, while문을 종료해주고 BFS를 나온다.
그리고 적록색약이 아닌 사람들이 보는 구역 개수를 카운트 + 1 해준다.
그리고 적록색약인 사람들에 대한 배열도 적록색약이 아닌 사람들에 대한 배열에서 했던 것 처럼 똑같은 방법으로 볼 수 있는 구역의 개수를 카운트해준다.

겪은 시행착오

좀 부끄러운 실수이긴한데... 처음에 while문에서 못벗어나길래 뭐가 문제인가 봤더니... Queue에 있던 값을 사용하고 안 뺐었다... ㅎ... (실수를 조심하자..!!)

코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class BOJ10026 {

    static int N;
    static char RGB[][];
    static char RB[][];
    static boolean rgb_visited[][];
    static boolean rb_visited[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

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

        // 행, 열
        N = Integer.parseInt(br.readLine());

        // 적록색약이 아닌 사람이 보는걸 저장할 배열
        RGB = new char[N][N];
        // 적록색약인 사람이 보는걸 저장할 배열
        RB = new char[N][N];
        // 적록색약이 아닌 사람의 방문처리 배열
        rgb_visited = new boolean[N][N];
        // 적록색약인 사람의 방문처리 배열
        rb_visited = new boolean[N][N];

        for(int i = 0; i < N; i++){
            String s = br.readLine();

            for(int j = 0; j < N; j++){
                char c = s.charAt(j);

                // 적록색약이 아닌 사람은 그대로 배열에 저장
                RGB[i][j] = c;

                // 입력값이 G가 들어온다면 적록색약인 사람들은
                // R과 같이 보기 때문에 R로 저장
                if(c == 'G'){
                    RB[i][j] = 'R';
                }
                // G가 아닐 때는 적록색약이 아닌 사람처럼 그대로 저장
                else{
                    RB[i][j] = c;
                }
            }
        }

        int rgb_cnt = 0;
        int rb_cnt = 0;

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                // 적록색약이 아닌 사람들을 저장해놓은 배열에서
                // 방문하지 않은 좌표를 만났다면
                if(!rgb_visited[i][j]){
                    // 해당 좌표를 기준으로 BFS를 돌리고
                    RGB_BFS(RGB[i][j], i, j);

                    // 적록색약이 아닌 사람들이 보는 구역 카운트 + 1
                    rgb_cnt = rgb_cnt + 1;
                }

                // 적록색약인 사람들을 저장해놓은 배열에서
                // 방문하지 않은 좌표를 만났다면
                if(!rb_visited[i][j]){
                    // 해당 좌표를 기준으로 BFS를 돌리고
                    RB_BFS(RB[i][j], i, j);

                    // 적록색약인 사람들이 보는 구역 카운트 + 1
                    rb_cnt = rb_cnt + 1;
                }
            }
        }

        System.out.println(rgb_cnt + " " + rb_cnt);
    }

    // 적록색약이 아닌 사람들을 위한 BFS
    public static void RGB_BFS(char color, int x, int y){
        Queue<Point> q = new LinkedList<>();

        // 입력들어온 색깔을 따로 저장
        char c = color;

        // 입력들어온 좌표를 Queue에 저장
        q.offer(new Point(x, y));

        rgb_visited[x][y] = true;

        // Queue가 빌때까지 반복
        while(!q.isEmpty()){
            int xx = q.peek().x;
            int yy = q.peek().y;

            q.poll();

            // 기준좌표에서 상하좌우 이동
            for(int i = 0; i < 4; i++){
                int nx = xx + dx[i];
                int ny = yy + dy[i];

                // 만약 이동한 좌표가 범위를 벗어난다면 continue
                if(nx >= N || nx < 0 || ny >= N || ny < 0){
                    continue;
                }

                // 만약 해당 좌표를 아직 방문하지 않았고 입력들어온 색깔과 같다면
                // 같은 범위로 보고 있는 것이므로
                if(!rgb_visited[nx][ny] && (RGB[nx][ny] == c)){
                    // 해당 좌표를 방문처리하고
                    rgb_visited[nx][ny] = true;
                    // Queue에 해당 좌표를 넣음
                    q.offer(new Point(nx, ny));
                }
            }
        }
    }

    // 적록색약인 사람들을 위한 BFS
    public static void RB_BFS(char color, int x, int y){
        Queue<Point> q = new LinkedList<>();

        // 입력들어온 색깔을 따로 저장
        char c = color;

        // 입력들어온 좌표를 Queue에 저장
        q.offer(new Point(x, y));

        rb_visited[x][y] = true;

        // Queue가 빌때까지 반복
        while(!q.isEmpty()){
            int xx = q.peek().x;
            int yy = q.peek().y;

            q.poll();

            // 기준좌표에서 상하좌우 이동
            for(int i = 0; i < 4; i++){
                int nx = xx + dx[i];
                int ny = yy + dy[i];

                // 만약 이동한 좌표가 범위를 벗어난다면 continue
                if(nx >= N || nx < 0 || ny >= N || ny < 0){
                    continue;
                }

                // 만약 해당 좌표를 아직 방문하지 않았고 입력들어온 색깔과 같다면
                // 같은 범위로 보고 있는 것이므로
                if(!rb_visited[nx][ny] && (RB[nx][ny] == c)){
                    // 해당 좌표를 방문처리하고
                    rb_visited[nx][ny] = true;
                    // Queue에 해당 좌표를 넣음
                    q.offer(new Point(nx, ny));
                }
            }
        }
    }
}

🍊귤 농장🍊

[Java] BOJ 10026 적록색약

문제

아이디어

겪은 시행착오

코드

티스토리툴바