BOJ 2630 : 색종이 만들기

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2630

 

이후 설명 및 입/출력은 링크 참고

 

색종이의 판단은 시작 좌표 (sr, sc) 그리고 size를 이용하여 판단한다.

아래의 check 함수는 비정상적인 색종이인 경우 -1을 return하고,

정상적인 경우 MAP[sr][sc]를 return한다. MAP[sr][sc]가 0이면 WHITE 색종이, 1이면 BLUE 색종이가 된다.

int check(int sr, int sc, int size)
{
	int tmp = MAP[sr][sc];
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			if (MAP[r][c] != tmp) return -1;

	return tmp;
}

 

가장 큰 색종이부터 (size == N) 검사해서 색종이가 아닌 경우 4등분으로 나눈다.

좌표가 (r, c)시작하고 size가 n인 색종이를 4등분 하면

 

좌표가 (r, c)에서 시작하고 size는 n / 2

좌표가 (r + n / 2, c)에서 시작하고 size는 n / 2

좌표가 (r, c + n /2)에서 시작하고 size는 n / 2

좌표가 (r + n / 2, c + n / 2)에서 시작하고 size는 n / 2

 

로 나뉘기 때문에 DFS는 아래와 같이 구성된다.

DFS(r, c, n / 2);
DFS(r + n / 2, c, n / 2);
DFS(r, c + n / 2, n / 2);
DFS(r + n / 2, c + n / 2, n / 2);

 

전체 코드는 아래와 같다.

#include <stdio.h>

#define MAX (128 + 10)

int N;
int MAP[MAX][MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

int check(int sr, int sc, int size)
{
	int tmp = MAP[sr][sc];
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			if (MAP[r][c] != tmp) return -1;

	return tmp;
}

int WHITE;
int BLUE;
void DFS(int r, int c, int n)
{
	int ans = check(r, c, n);
	if (ans != -1)
	{
		if (ans == 0) WHITE++;
		else if (ans == 1) BLUE++;

		return;
	}

	DFS(r, c, n / 2);
	DFS(r + n / 2, c, n / 2);
	DFS(r, c + n / 2, n / 2);
	DFS(r + n / 2, c + n / 2, n / 2);
}

int main(void)
{
	input();

	DFS(1, 1, N);

	printf("%d\n%d\n", WHITE, BLUE);

	return 0;
}