[백준] 온라인 저지 10026번 : 적록색약(Java), BFS

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

 

 

 

입력

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

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

 

 

 

출력

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

---

문제 풀이

BFS() 함수에 boolean 값으로 적록색약 여부를 체크하여 BFS 로직을 두번 실행하도록 작성하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int green = 0;
    static int red = 0;
    static int blue = 0;
    static int area1 = 0;
    static int area2 = 0;

    static int N;
    static Character[][] arr;
    static boolean[][] visited;
    static boolean[][] visited2;
    static int dx[] = {1, 0, -1, 0};
    static int dy[] = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new Character[N][N];
        visited = new boolean[N][N];
        visited2 = new boolean[N][N];

        for(int i=0; i<N; i++) {
            String tempStr = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = tempStr.charAt(j);
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {

                    if('G' == arr[i][j]) {
                        green += 1;
                    } else if('B' == arr[i][j]) {
                        blue += 1;
                    } else if('R' == arr[i][j]) {
                        red += 1;
                    }
                    BFS(i, j, false);
                }
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited2[i][j]) {
                    if('G' == arr[i][j] || 'R' == arr[i][j]) {
                        area1 += 1;
                    } else if('B' == arr[i][j]) {
                        area2 += 1;
                    }
                    BFS(i, j, true);
                }
            }
        }
        System.out.print(green + blue + red + " ");
        System.out.print(area1 + area2);
    }

    private static void BFS(int x, int y, boolean isBlind) {

        Character color = arr[x][y]; // B or G or R

        if(!isBlind) {
            // 적록 색약이 아닌 사람
            Queue<int[]> q = new LinkedList<>();
            visited[x][y] = true;
            q.add(new int[] {x, y});

            while(!q.isEmpty()) {
                int[] now = q.poll();

                for(int i=0; i<4; i++) {
                    int nextX = now[0] + dx[i];
                    int nextY = now[1] + dy[i];


                    if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                        if(arr[nextX][nextY] == color && !visited[nextX][nextY]) {
                            visited[nextX][nextY] = true;
                            q.add(new int[] {nextX, nextY});
                        }
                    }
                }
            }
        } else {
            // 적록 색약
            Queue<int[]> q2 = new LinkedList<>();
            visited[x][y] = true;
            q2.add(new int[] {x, y});

            while(!q2.isEmpty()) {
                int[] now = q2.poll();

                for(int i=0; i<4; i++) {
                    int nextX = now[0] + dx[i];
                    int nextY = now[1] + dy[i];

                    if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                        if(!visited2[nextX][nextY]) {
                            Character nextColor = arr[nextX][nextY];
                            if(color == 'G' || color == 'R') {
                                if(nextColor == 'G' || nextColor == 'R') {
                                    visited2[nextX][nextY] = true;
                                    q2.add(new int[] {nextX, nextY});
                                }
                            } else {
                                if(nextColor == color) {
                                    visited2[nextX][nextY] = true;
                                    q2.add(new int[] {nextX, nextY});
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

 

하지만 위의 해설은 코드 중복이 많아, 같은 색으로 인식하는지 여부를 따로 함수로 작성해 아래와 같이 코드를 개선할 수 있다.

 

> isSameColor() 추가

private static boolean isSameColor(Character color, Character compareColor, boolean isBlind) {
        boolean isSame = false;
        if(isBlind) {
            if(color == 'G' || color == 'R') {
                if(compareColor != 'B') {
                    isSame = true;
                } else {
                    isSame = false;
                }
            } else {
                return color == compareColor;
            }
        } else {
            return color == compareColor;
        }
        return isSame;
    }

 

 

 

최종 코드 : 함수가 훨씬 간결해짐 !

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int green = 0;
    static int red = 0;
    static int blue = 0;
    static int area1 = 0;
    static int area2 = 0;

    static int N;
    static Character[][] arr;
    static boolean[][] visited;
    static boolean[][] visited2;
    static int dx[] = {1, 0, -1, 0};
    static int dy[] = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new Character[N][N];
        visited = new boolean[N][N];
        visited2 = new boolean[N][N];

        for(int i=0; i<N; i++) {
            String tempStr = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = tempStr.charAt(j);
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {

                    if('G' == arr[i][j]) {
                        green += 1;
                    } else if('B' == arr[i][j]) {
                        blue += 1;
                    } else if('R' == arr[i][j]) {
                        red += 1;
                    }
                    BFS(i, j, false);
                }
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited2[i][j]) {
                    if('G' == arr[i][j] || 'R' == arr[i][j]) {
                        area1 += 1;
                    } else if('B' == arr[i][j]) {
                        area2 += 1;
                    }
                    BFS(i, j, true);
                }
            }
        }
        System.out.print(green + blue + red + " ");
        System.out.print(area1 + area2);
    }

    private static boolean isSameColor(Character color, Character compareColor, boolean isBlind) {
        boolean isSame = false;
        if(isBlind) {
            if(color == 'G' || color == 'R') {
                if(compareColor != 'B') {
                    isSame = true;
                } else {
                    isSame = false;
                }
            } else {
                return color == compareColor;
            }
        } else {
            return color == compareColor;
        }
        return isSame;
    }

    private static void BFS(int x, int y, boolean isBlind) {

        Character color = arr[x][y]; // B or G or R
        boolean[][] visitedArr = isBlind? visited2 : visited;

        Queue<int[]> q = new LinkedList<>();
        visitedArr[x][y] = true;
        q.add(new int[] {x, y});

        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int i=0; i<4; i++) {
                int nextX = now[0] + dx[i];
                int nextY = now[1] + dy[i];

                if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                    if(isSameColor(color, arr[nextX][nextY], isBlind) && !visitedArr[nextX][nextY]) {
                        visitedArr[nextX][nextY] = true;
                        q.add(new int[] {nextX, nextY});
                    }
                }
            }
        }
    }
}