BOJ 10026) 적록색약

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

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

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

출력

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

 

 

 

 

풀이

 

이전에 풀었던 단지번호붙이기 (https://eckrin.tistory.com/entry/BOJ-2667-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0?category=985109)와 거의 동일한 문제.. 근데 오랜만에 푸니깐 정리가 안돼서 다시 정리.

 

일단 특정 조건을 바탕으로 구역을 나누어, 구역의 개수를 구하는 간단한 BFS/DFS문제이다.

문제를 보자마자 RGB로 구별된 칸들을 배열로 만들고, 1칸씩 탐색하면서 구역의 개수를 구해야 하므로 DFS(스택)이나 BFS(큐)를 이용해서 구해야 한다는 생각을 했다. 

배열을 탐색하다가 구하지 않은 구역의 칸을 탐색하게 되면 dfs/bfs함수를 호출하여 같은 구역의 모든 칸을 탐색한 후, 본래 배열 탐색으로 돌아간다.

이 때 스택을 이용한 DFS를 이용하였다. 스택의 제네릭을 이용하기 위해서 배열의 x,y좌표를 저장할 수 있는 Location이라는 클래스를 만들고, 처음 [0][0]좌표를 넣고 탐색한다. 그런데 이때 좌표들이 탐색이 끝난 좌표인지를 기록하는 방법이 필요하다. 처음에는 R(0),G(1),B(2)값을 탐색하고 나면 배열의 값을 -1로 바꾸어주려고 했는데, 문제는 DFS나 BFS를 이용해서 탐색하게 되면 해당 좌표가 이미 탐색한 좌표인지를 알 수 없게된다. 이런 경우 탐색여부를 알 수 있는 boolean배열을 이용하면 된다. 전역변수로 visited라는 NxN배열을 그대로 선언한 다음, 검사가 끝난 칸에 대해서는 true값을 주었고, 탐색조건에서 제외하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    static int[][] test;
    static int[][] arr;
    static int N;
    static boolean[][] visited;

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

        int count;
        arr = new int[N][N]; //R:0, G:1, B:2

        //get input
        for(int i=0; i<N; i++) {
            String input = br.readLine();
            String[] inputWords = input.split("");
            for(int j=0; j<N; j++) {
                arr[i][j] = (inputWords[j].equals("R")?0:(inputWords[j].equals("G")?1:2));
            }
        }

        //get normal area number
        visited = new boolean[N][N];
        test = arr.clone();
        count = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    count++;
                    Location loc = new Location(i, j);
                    updateArea(loc, test[i][j]);
                }
            }
        }
        System.out.print(count + " ");

        //get sekyak area number
        visited = new boolean[N][N];
        test = arr.clone();
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if(test[i][j]==1)
                    test[i][j] = 0;
        count = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    count++;
                    Location loc = new Location(i, j);
                    updateArea(loc, test[i][j]);
                }
            }
        }
        System.out.print(count);

    }

    private static void updateArea(Location loc, int val) {
        Stack<Location> stack = new Stack<>();
        stack.push(loc);
        visited[loc.x][loc.y] = true;

        while(!stack.isEmpty()) {
            Location peekLoc = stack.peek();
            int x = peekLoc.x;
            int y = peekLoc.y;
            boolean flag = true;

            if(x>0 && test[x-1][y]==val && !visited[x-1][y]) {
                visited[x-1][y] = true;
                Location l = new Location(x-1, y);
                stack.push(l);
                flag = false;
            }
            if(y>0 && test[x][y-1]==val && !visited[x][y-1]) {
                visited[x][y-1] = true;
                Location l = new Location(x, y-1);
                stack.push(l);
                flag = false;
            }
            if(x<N-1 && test[x+1][y]==val && !visited[x+1][y]) {
                visited[x+1][y] = true;
                Location l = new Location(x+1, y);
                stack.push(l);
                flag = false;
            }
            if(y<N-1 && test[x][y+1]==val && !visited[x][y+1]) {
                visited[x][y+1] = true;
                Location l = new Location(x, y+1);
                stack.push(l);
                flag = false;
            }
            if(flag) stack.pop();
        }
    }

    static class Location {
        int x;
        int y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

추가) DFS,BFS 참고: https://eckrin.tistory.com/entry/Algorithm-DFS%EC%99%80-BFS?category=985105