백준 온라인 저지 | 2630번 색종이 만들기 | C++

백준 온라인 저지 | 2630번 색종이 만들기 | C++

2630번: 색종이 만들기

 

1. 문제 접근

■ 1.1 기본 조건

 종이가 한 가지 색으로만 칠해져 있는 경우, 종이의 개수를 세고 있는 배열에서 흰색 종이의 개수 혹은 파란색 종이의 개수를 1만큼 증가시킨다.

 

■ 1.2 재귀 조건

 종이가 두 가지 색으로 칠해져 있는 경우, 종이를 좌상단, 우상단, 좌하단, 우하단 네 부분으로 나누고 네 부분에 대해서 각각 한 가지 색으로만 칠해져 있는지 재귀적으로 구현해야 한다.

 

■ 1.3 함수 인자

 기본 조건과 재귀 조건을 구분하려면 종이가 어떤 색으로 구성되어 있는지 파악해야 한다. 이때 종이의 색을 파악하려면 두 가지 정보가 필요하다. 첫 번째는 종이의 한 변의 길이로, 사용자가 입력하는 양의 정수 N에서 구할 수 있다. 한 변의 길이는 종이가 같은 색으로 구성되어 있는지 비교할 범위를 설정한다. 두 번째는 종이의 좌상단 좌표이다. 종이를 2차원 배열로 나타냈을 때 좌상단 좌표는 배열의 시작점이라고 할 수 있다. 이 시작점과 다른 좌표를 주어진 범위 안에서 비교함으로써 이 종이가 같은 색으로 되어 있는지 혹은 다른 색으로 되어 있는지 확인할 수 있다. 최초 좌상단 좌표는 한 번도 자르지 않은 종이의 시작점인 (0, 0)으로 설정한다.

그림 1-1 정사각형 한 변의 길이와 시작점으로 종이의 색을 확인하는 과정

 

2. 문제 풀이

1. 종이의 정보를 저장할 2차원 벡터 paper와 흰 종이 및 파란 종이의 개수를 저장할 1차원 벡터 color를 선언한다. paper의 크기는 N×N으로 설정하고 주어진 종이 정보로 paper를 초기화한다.
2. 재귀 함수에 종이의 한 변의 길이 N과 최초 좌상단 좌표 (0, 0)을 전달한다.
   • 종이의 색이 모두 같은지 좌상단 좌표의 색과 다른 좌표의 색을 하나씩 비교한다.
   • 종이의 색이 모두 같은 경우, 기본 조건이므로 그 종이의 색에 해당하는 color 벡터의 요소를 1만큼 증가시킨다.
   • 종이의 색이 다른 경우, 재귀 조건이므로 2중 for문으로 재귀 함수를 네 번 호출한다. 이때, 재귀 함수의 인자로 한 변의 길이의 절반인 n / 2와 네 부분으로 나누어진 종이의 시작점을 전달한다.

 

3. 문제 해결

#include <iostream>
#include <vector>
using namespace std;

void makePaper();
bool isSameColor(int n, int x, int y);
void recursion(int n, int x, int y);

vector<vector<int>> paper;
vector<int> color;
int N;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	makePaper();

	// 한 변의 길이가 N인 정사각형 종이의 (0, 0)부터 시작합니다.
	recursion(N, 0, 0);
	for (const auto& e : color) {
		cout << e << '\n';
	}
	return 0;
}

void makePaper() {
	cin >> N;
	paper = vector<vector<int>>(N, vector<int>(N, 0));
	// 하얀 종이(0)과 파란 종이(1)의 개수를 저장할 color 벡터입니다.
	color = vector<int>(2, 0);

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> paper[i][j];
		}
	}
}

// 종이가 모두 같은 색으로 되어있는지 확인합니다.
bool isSameColor(int n, int x, int y) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			// 첫 번째 종이 조각과 그외 종이 조각의 색을 순서대로 비교합니다.
			if (paper[x][y] != paper[x + i][y + j]) {
				return false;
			}
		}
	}
	// 종이 색이 모두 같으면 true를 반환합니다.
	return true;
}

// 한 변의 길이 n, 시작 좌표 (x, y)를 인자로 전달합니다.
void recursion(int n, int x, int y) {
	// 기본 조건으로 종이의 색이 모두 같은 경우입니다.
	if (isSameColor(n, x, y)) {
		// 하얀 종이 혹은 파란 종이 개수를 증가시킵니다.
		++color[paper[x][y]];
		return;
	}

	// 재귀 조건으로 종이의 색이 다른 경우입니다.
	else {
		// 종이를 네 부분으로 나눕니다.
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				// 한 변의 절반의 길이와 새로운 시작 좌표를 인자로 전달합니다.
				recursion(n / 2, (n / 2) * i + x, (n / 2) * j + y);
			}
		}
	}
}

2630번 색종이 만들기 성공

 

4. 문제 고찰

 이 문제는 함수의 인자를 파악하기가 다소 까다로웠는데 기본 조건과 재귀 조건을 세우는 과정에서 어떤 인자가 필요한지 자연스럽게 도출해낼 수 있었다. 기본 조건과 재귀 조건을 구분하려면 종이가 모두 같은 색으로 되어있는지 알아야 하고, 종이가 모두 같은 색으로 되어있는지 알려면 주어진 종이의 크기만큼 모든 좌표를 하나씩 비교해봐야 한다. 따라서 종이의 한 변의 길이와 (r, c) 형태의 좌표를 인자로 전달해야 한다는 사실을 알게 되었다.