백준 알고리즘 2630 (색종이 만들기) - C++, Python

[문제] 백준 알고리즘 2630 (색종이 만들기)

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

2630번: 색종이 만들기

'분할 정복(Divide and Conquer)' 문제이다.

분할 정복은 보통 재귀함수의 응용인데, 원하는 조건을 만족하지 않으면

문제를 분할(=작은 부문제)해서 해결하는 방식으로 다시 재귀시킨다.

 

4등분을 하면서 색종이의 흰색/파란색 덩어리를 체크하는 문제라서,

4개의 부문제를 해결해나가기 때문에 '쿼드트리'라고도 하는 것 같다.

 

[문제 해결]

1. n과 map[129][129]을 입력으로 받는다.

2. 분할 정복을 위한 재귀 함수로, 4등분의 기준이 될 index (x,y)와 크기 n을 넘겨준다.

3. map[x][y]가 1(=파란색)일 때의 갯수를 체크한다.

4. 갯수가 0이면(=전체 흰색) 흰색++, 갯수가 N^2개면(=전체 파란색) 파란색++

5. 전체가 흰색도 파란색도 둘 다 아니면, 분할하여 4개의 부문제를 해결한다.

    - N^2을 (N/2)^2 * 4의 부문제 4개로 분할하며 재귀시킨다.

    - 왼쪽 위의 기준점 (x, y)와 N/2로 재귀

    - 오른쪽 위의 기준점 (x, y+N/2)와 분할한 N/2로 재귀

    - 왼쪽 아래의 기준점 (x+N/2, y)와 분할한 N/2로 재귀

    - 오른쪽 아래의 기준점 (x+N/2, y+N/2)와 분할한 N/2로 재귀

6. 흰색과 파란색의 갯수 출력

 

[C++]

#include <cstdio>
#include <cstring> // memset
using namespace std;
int map[129][129];
int w_cnt = 0, b_cnt = 0; 

void div_conq(int x, int y, int N) {
	int tmp_cnt = 0;
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (map[i][j]) {
				tmp_cnt++;
			}
		}
	}
	if (!tmp_cnt) w_cnt++; // no count
	else if (tmp_cnt == N * N) b_cnt++; // all count
	else {
		div_conq(x, y, N / 2);  // left top
		div_conq(x, y + N / 2, N / 2); // right top
		div_conq(x + N / 2, y, N / 2); // left bottom
		div_conq(x + N / 2, y + N / 2, N / 2); // right bottom
	}
	return;
}

int main() {
	int n;
	memset(map, 0, sizeof(map));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	div_conq(0, 0, n); // divide and conquer
	printf("%d\n", w_cnt);
	printf("%d\n", b_cnt);
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
B = [list(map(int, input().split())) for _ in range(n)]
w_cnt, b_cnt = 0, 0

def div_conq(x, y, N):
    global w_cnt, b_cnt
    tmp_cnt = 0
    for i in range(x, x + N):
        for j in range(y, y + N):
            if B[i][j]:
                tmp_cnt += 1
    if not tmp_cnt:
        w_cnt += 1
    elif tmp_cnt == N**2:
        b_cnt += 1
    else:
        div_conq(x, y, N // 2)
        div_conq(x + N // 2, y, N // 2)
        div_conq(x, y + N // 2, N // 2)
        div_conq(x + N // 2, y + N // 2, N // 2)
    return

div_conq(0, 0, n)
print(w_cnt)
print(b_cnt)