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

문제 접근

조건을 만족할 때 까지 큰 문제를 작은 문제들로 나누어 해결하는 분할 정복의 대표적인 문제로 다음과 같은 과정을 진행
1. 정의 : 주어진 N x N 종이가 모두 같은 색인지 확인
2. 정복(Conquer) : 모두 같은 색이라면, 해당 색깔의 종이 개수를 1 증가시키고 탐색 종료
3. 분할(Divide) : 색이 섞여 있으면, 종이를 같은 크기의 4개의 사분면으로 나눈다(N/2 x N/2)
4. 반복(Recur) : 나누어진 4개의 작은 종이에 대해 1번 과정부터 다시 반복

문제 조건

• N은 2의 거듭제곱 이다. ($N = 2^k$, 1 <= k <= 7)
• 흰색은 0, 파란색은 1의 형태로 주어진다.

문제 설계

자료구조

• 2차원 배열 사용 : int[][] matrix로 표현하며 matrix[row][col]을 통해 특정 좌표의 색상 정보에 즉시 접근 가능 $O(1)$

로직

• recursion(재귀함수) : Top-Down 방식의 분할 recursion(r, c, len)는 r, c에서 시작하는 len 크기의 정사각형 문제를 해결하는 명령어

  • 호출 : len 크기의 정사각형이 모두 같은 색인지 check 함수를 통해 검사
  • 기저조건 (Base Case) : 만약 check가 true를 반환하면(색이 모두 같을 경우) 재귀 탈출 전역변수 W, B를 해당 색상에 맞게 1증가시키고 return
  • 분할 : check()가 false를 반환하면(색이 섞인 경우) 문제를 4개의 동일한 하위 문제로 나눈다. divLen = len / 2로 설정 후 4개의 사분면에 대해 각각 recursion 함수를 재귀적으로 호출 ($O(logN)$)

• check(색상 검사) : 주어진 구역에 대한 색상 검사를 진행하는 함수 입력받은 범위를 탐색하며 색상이 모두 같으면 true 아니면 false를 반환한다. 한번의 길이가 len인 정사각형에 대한 탐색을 진행 $O(len^2)$

재귀 호출단계에서 이차원 배열 순회를 통해 색상검사를 진행하기 때문에
최종 시간 복잡도는 $O(N^2 * logN)$이 된다.

구현 코드

package BOJ.silver;

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

public class silver2_2630_DAC {
	static int N;
    // 이차원 배열로 색종이 상태 저장 및 관리
	static int[][] matrix;
	
    // 결괏값을 저장할 파란색과 흰색 개수에 대한 변수
	static int B, W;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		matrix = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		W = 0;
		B = 0;
		
        // row, col, len 재귀 호출
		recursion(0, 0, N);
		
        // 각각의 갯수 출력
		System.out.println(W);
		System.out.println(B);
		
	}
	
    // 분할 정복 재귀 코드
	public static void recursion(int r, int c, int len) {
    	// 해당 영역이 같은 색상인지 검사
		if (check(r, c, len)) {
        	// 모두 같을 경우 흰색 or 파란색인지 확인 후 갯수 증가 후 종료
			if (matrix[r][c] == 0) {
				W++;
			} else {
				B++;
			}
			return;
		}
		
        // check 결과가 false 인 경우 4개로 분할하는 작업 수행
		int divLen = len / 2;
		
		// 분할
		recursion(r, c, divLen);
		recursion(r, c + divLen, divLen);
		recursion(r + divLen, c, divLen);
		recursion(r + divLen, c + divLen, divLen);		
	}
	
	// 색상이 모두 같은지 확인
	public static boolean check(int r, int c, int len) {
    	// 비교할 색상에 대한 정보를 임시 변수에 담는다.
		int tmp = matrix[r][c];
		for (int i = r; i < r + len; i++) {
			for (int j = c; j < c + len; j++) {
            	// 하나라도 다르면 false 반환
				if (matrix[i][j] != tmp) {
					return false;
				}
			}
		}
		
        // 아무 이상 없으면 true 반환
		return true;
	}
}

회고

분할정복에 대한 연습을 하기 좋은 대표적인 문제이다. 다만 좌우로 분할하는 것이아닌 이차원 배열에서 row, col 기준으로 4개로 분할되는 형태이기 때문에 분할 방법에 대한 생각이 필요한 문제였다.