백준 2630 색종이 만들기 Java 풀이

문제

N×N(N=2k, k는 1 이상 7 이하의 자연수) 크기의 배열이 주어지고, 0 아니면 1로 채워져있다. 0을 흰색, 1을 파란색으로 인식할때 배열이 하나의 색상으로만 이뤄질때까지 4등분씩 잘라내고 최종적으로 모든 정사각형이 하나의 색상으로만 이루어졌을때 흰색 정사각형개수, 파란색 정사각형 개수를 출력하라

접근

로직

(1) 판단: 주어진 배열 BOARD 가 BOARD[x][y] ~ BOARD[x+size][y+size] 안에 모든 숫자가 동일한지 판단한다.

(2) 병합: 주어진 배열 BOARD 이 일정 범위 (x,y ~ + size) 안에서 동일한 숫자만 있다면 그에 맞는 색상{흰색, 파란색} 의 개수를 늘린다.

(3) 분할: 주어진 배열 BOARD 이 일정 범위 (x,y ~ + size) 안에서 동일한 숫자만 있지 않다면 배열을 4등분하여 (1) 단계를 반복한다.

 

분할이후 판단을 재귀적으로 호출하는 흐름이 될 것이다.

시간복잡도

주어진 배열을 나누고(분할) 숫자를 센다(정복) 이 분할정복 알고리즘의 시간복잡도는 어떻게 될까?

빅오 표기법을 생각하면 각 단계에서 이루어지는 연산과 나누어진 부분에서 이뤄지는 연산의 시간복잡도 중 큰것을 넣어야한다.

단계별 시간복잡도

각 단계별로 어떤것들이 이뤄지는지 보자

(1) 판단 단계에서는 최대 NxN 을 순회하여 숫자 동일성을 판단하게 된다 O(N^2)

(2) 병합 단계에서는 흰색 or 파란색 판단이므로 연산이 한번만 이뤄진다. O(1)

(3) 분할 단계에서는 4등분 하여 판단 단계로 넘겨야 하므로 보통은 4번의 연산이 이뤄진다. O(4)

각 단계 별로 봤을때는 N^2 이 최악의 시간복잡도가 된다.

한번의 분할이 만드는 시간 복잡도

그렇다면 분할 이후 재귀적으로 호출하게 된다면 하나의 재귀 호출마다 (N/2)^2 의 시간복잡도를 갖는 연산이 이뤄진다.

한번의 재귀 호출마다 4번 연산이 요구되므로 4 x (N/2)^2  가 최종적인 시간복잡도가 된다.

 

재귀호출의 횟수

그러면 재귀 호출은 최대 몇번까지 일어날까?

한변의 길이가 N 인 정사각형을 4등분했을 때 한변의 길이가 1이 될때까지의 반복횟수는 log2(N) 이다.

 

이상을 종합해보면  하나의 수열이 된다.

log2(N) x 4^i x (N/2^i)^2 , { when  0 <= i < log2(N) }

 

결국 빅오 표기법에 의해서 O(N^2) 의 시간복잡도를 기대할수 있다.

 

풀이

public class Main {
    private static final int WHITE_COLOR_MARKER = 0;
    private static int whiteSquareCount, blueSquareCount= 0;
    private static int[][] BOARD;

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

        // 입력 초기화
        int N = Integer.parseInt(br.readLine());
        BOARD = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                BOARD[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 분할&정복
        divideAndCount(0, 0, N);

        // 결과값 출력
        System.out.println(whiteSquareCount +"\n" + blueSquareCount);
    }

    private static void divideAndCount(int x, int y, int size) {
        if (isOneColor(x, y, size)) {
            if (BOARD[x][y] == WHITE_COLOR_MARKER) {
                whiteSquareCount++;
            } else {
                blueSquareCount++;
            }
            return;
        }

        int newSize = size/2;
        divideAndCount(x, y, newSize);
        divideAndCount(x +newSize, y, newSize);
        divideAndCount(x, y + newSize, newSize);
        divideAndCount(x + newSize, y + newSize, newSize);
    }

    /**
     *
     * @param x BOARD 탐색 시작 행 INDEX
     * @param y BOARD 탐색 시작 열 INDEX
     * @param size i+size, j+size 까지 탐색
     * @return {true: 모두 같은 색상만 있음 ,false: 서로 다른 색상이 있음}
     */
    private static boolean isOneColor(int x, int y, int size) {
        int color = BOARD[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (color != BOARD[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}