[Algorithm] boj_10026 (BFS)

문제

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

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

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

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

---

접근 방법

• 적록색약인 경우와 아닌 경우에 대해, 별도의 메서드와 방문 여부 배열을 두어 다르게 처리한다.

코드

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

public class boj_10026_BFS {

    static int N;
    static char[][] grid;
    static boolean[][] isVisited;
    static boolean[][] isVisitedBlind;
    static int[] dX = {-1, 1, 0, 0};
    static int[] dY = {0, 0, -1, 1};
    static Queue<Point> q;
    static int nonBlind;
    static int blind;

     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];
         isVisited = new boolean[N][N];
         isVisitedBlind = new boolean[N][N];

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

             for (int k = 0; k < N; k++) {
                 grid[i][k] = lane.charAt(k);
             }
         }
         
         //search
         for (int i = 0; i < N; i++) {
             for (int k = 0; k < N; k++) {
                 //적록색약이 아닌 경우
                 if (!isVisited[i][k]) {
                     isVisited[i][k] = true;
                     nonBlind++;
                     bfs(new Point(i, k), grid[i][k], false);
                 }

                 //적록색약인 경우
                 if (!isVisitedBlind[i][k]) {
                     isVisitedBlind[i][k] = true;
                     blind++;
                     bfs(new Point(i, k), grid[i][k], true);
                 }
             }
         }

         System.out.println(nonBlind + " " + blind);
     }

    static void bfs(Point point, char colour, boolean isBlind) {
        q = new LinkedList<>();
        q.offer(point);

        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + dX[i];
                int nextY = cur.y + dY[i];

                if (isBlind) {
                    searchAsBlind(colour, nextX, nextY);
                }else {
                    searchAsNonBlind(colour, nextX, nextY);
                }
            }
        }
    }

    private static void searchAsNonBlind(char colour, int nextX, int nextY) {
        if (isMovable(nextX, nextY) && !isVisited[nextX][nextY] && grid[nextX][nextY] == colour) {
            isVisited[nextX][nextY] = true;
            q.offer(new Point(nextX, nextY));
        }
    }

    private static void searchAsBlind(char colour, int nextX, int nextY) {
        if (isMovable(nextX, nextY) && !isVisitedBlind[nextX][nextY]){
            //인접한 색과 같거나, 현재 색과 인접한 색이 R 또는 G일 경우
            if ((grid[nextX][nextY] == colour)
                    || ((colour == 'R' || colour == 'G') && (grid[nextX][nextY] == 'R' || grid[nextX][nextY] == 'G'))) {
                isVisitedBlind[nextX][nextY] = true;
                q.offer(new Point(nextX, nextY));
            }
        }
    }

    static boolean isMovable(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }

    static class Point {
         int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}