[BOJ] 2630 : 색종이 만들기 (Java) with 분할 정복

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

2630번: 색종이 만들기

걸린 시간 : 19분 26초

---

기초적인 분할 정복 문제이다. 분할 정복은 재귀의 한 갈래이다.

재귀를 알 때 제일 중요한 것은 점화식이다. 점화식만 잘 파악하면 끝나는 문제.

알고리즘

색종이를 자를 cut() 메소드를 재귀호출한다. 재귀호출에 필요한 파라미터를 생각해보자.

파라미터의 조합으로 색종이를 자른 한 부분을 특정할 수 있으면 된다! 즉, 시작점이 필요하고, 색종이의 사이즈가 필요하므로 총 3개의 파라미터가 필요하다.

 

Base case를 살펴보자. 매 호출마다 해당 색종이가 모두 같은 색인지 확인하고 맞다면 카운트하고 return; 한다. 그렇지 않다면 종이를 네 부분으로 나눈다. 즉, 재귀호출을 4번 진행한다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ2630 {
 
    static int N;
    static int[][] board = new int[130][130];
    static int whiteNum;
    static int blueNum;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cut(0, 0, N);
        System.out.println(whiteNum);
        System.out.println(blueNum);
    }
 
    private static void cut(int ci, int cj, int n) {
        if (allSame(ci, cj, n)) {
            if (board[ci][cj] == 1) {
                blueNum++;
            } else {
                whiteNum++;
            }
            return;
        }
        cut(ci, cj, n/2);
        cut(ci, cj+n/2, n/2);
        cut(ci+n/2, cj, n/2);
        cut(ci+n/2, cj+n/2, n/2);
    }
 
    private static boolean allSame(int ci, int cj, int n) {
        int tmp = board[ci][cj];
        for (int i = ci; i < ci + n; i++) {
            for (int j = cj; j < cj + n; j++) {
                if (tmp != board[i][j])
                    return false;
            }
        }
        return true;
    }
}