2630 - 색종이 만들기(S2)

1. 문제

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

2. 풀이

색종이를 재귀함수를 통해 반복하여 분할정복하는 문제이다.
해당 문제를 풀기 위해 다음과 같은 방법을 설정할 수 있다.

1. 주어진 색종이가 1 또는 0으로 이루어졌는지 확인한다.
2. 해당 조건일 경우 값을 추가하고, 아닐 경우 4분할을 실행한다.
3. 크기의 경우 size를 통해 확인하고, 분할 시행시 1/2로 줄여준다. 기저조건으로 size == 1을 설정한다.

이를 코드를 통해 보면 다음과 같다.

3. 코드

import java.util.*;

public class Main {
    static int map[][];
    static int[] res = new int[2];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        map = new int[size][size];
        for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) map[i][j] = sc.nextInt();
        
        cut(0, 0, size);

        System.out.println(res[0]);
        System.out.println(res[1]);
    }

    private static void cut(int sR, int sC, int size) {
        if (size == 0) return;

        int check = map[sR][sC];
        boolean isTrue = true;
        CHECK:
        for (int i = sR; i < sR + size; i++)
            for (int j = sC; j < sC + size; j++)
                if(map[i][j] != check) {
                    isTrue = false;
                    break CHECK;
                }

        size /= 2;
        if(!isTrue) {
            cut(sR, sC, size);
            cut(sR, sC + size, size);
            cut(sR + size, sC, size);
            cut(sR + size, sC + size, size);
        }
        else res[check] += 1;

        return;
    }
}