[백준 2630, 1780] 색종이 만들기, 종이의 개수 - 재귀 (C++)

[백준 2630] 색종이 만들기

문제 출처

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

2630번: 색종이 만들기

문제

접근 방법

ㆍ해당 문제는 분할 정복과 관련된 문제이다.

ㆍ분할 정복은 큰 문제를 작은 문제로 분할하여 해결하는 방법이다.

ㆍ그 중에서도 재귀를 사용하여 푸는 것이 좋겠다고 생각했다.

코드

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

int arr[128][128];
int blue = 0;
int white = 0;

void paper(int y, int x, int n) {
	int mark = arr[y][x];
	int flag = 0; // 종이에 다른 숫자가 있는지 체크
	if (n == 1) {
		if (mark == 0)
			white++;
		else
			blue++;
		return;
	}
	for (int i = y; i < y + n; i++)
		for (int j = x; j < x + n; j++) {
			if (mark != arr[i][j]) {
				flag = 1;
			}
		}
	if (flag == 1) {
		paper(y, x, n / 2);
		paper(y, x + n / 2, n / 2);
		paper(y + n / 2, x, n / 2);
		paper(y + n / 2, x + n / 2, n / 2);
	}
	else {
		if (mark == 0)
			white++;
		else
			blue++;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, num;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	paper(0, 0, N);
	cout << white << '\n' << blue;
	return 0;
}

주의해야 할 점

ㆍ배열 arr[128][128]과 변수 white, blue를 전역 변수로 선언해주자.

  -> 함수를 통해서 결국에 white와 blue의 값을 반환해주어야 하는데, 한 함수를 통해 두 개의 변수를 반환해줄 수는 없다.

  -> 전역 변수로 선언해놓는다면, 함수에서 white와 blue를 자유롭게 사용할 수 있다.

  -> 또한, white와 blue를 자유롭게 사용한 후에 따로 white와 blue를 반환해주지 않아도 전역 변수이기 때문에, main 함수        에서도 white와 blue의 변화된 값을 사용할 수 있다.

  -> 함수의 인자로 이차원 배열을 받음으로써 이차원 배열을 꼭 전역 변수로 설정해놓지 않아도 되긴 하지만, 전역 변수로        선언해주는 것이 여러모로 다루기 편한 것 같다.

 

ㆍ이 문제는 굳이 n == 1인 경우를 따로 base case로 두지 않아도 된다.

  -> paper 함수는 void 형이기 때문에 int형처럼 return (변수) 이런 식으로 따로 써주지 않아도, 함수 안의 명령을 모두 실          행하게 되면 자연스럽게 종료된다.

  -> n == 1인 경우를 굳이 조건문으로 써주지 않아도, n == 1일 때의 이중 for문의 범위가 i 는 y만, j는 x만 가능하기 때문            에, 사실상 mark가 v[y][x] (= mark)와 같은지만 확인하기 때문에, 당연하게도 flag는 0이 된다. flag가 0이기 때문에              mark가 0인지 1인지에 따라서 white 또는 blue의 개수가 1만큼 증가하고, 함수가 종료된다. 즉, 굳이 n == 1인 경우를          따로 base case로 두고 return; 명령을 써주지 않아도 되는 것이다.

 

ㆍpaper 함수 내의 이중 for문의 범위를 정확히 설정하자.

  -> 처음에, 나는 아무 생각 없이 너무나도 자연스럽게 이중 for문의 범위를 i = 0 ~ n, j = 0 ~ n 으로 설정했다.

  -> 이 문제의 경우에는 재귀의 특성을 이용함에 따라, 함수가 호출될 때마다 이중 for문을 통해 확인할 범위가 달라지기          때문에 함수의 인자로 받는 y와 x에 맞춰 적절한 범위를 설정해주어야 한다.

느낀 점

처음에는, 재귀에 익숙하지 않기 때문에 굉장히 겁을 먹고 문제에 풀기 시작했다.

그러나 생각보다, 어렵지 않은 문제였다. (white와 blue를 전역 변수로 선언할 생각을 하기까지가 은근히 오래 걸렸다.)

그리고, 나는 처음에 vector를 사용하기로 했는데, 이차원 vector를 사용하는 과정이 꽤나 까다로워서 배열을 쓰기로 했다.

요즘에, 계속 vector만 쓰다 보니까 배열의 존재를 잠깐 까먹긴 했었는데 문제를 보고 그에 맞게 배열을 쓰든지, vector를 쓰든지 적절하게 사용해야겠다는 생각을 했다.  

[백준 1780] 종이의 개수

문제 출처

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

1780번: 종이의 개수

문제

접근 방법

ㆍ앞서 풀이한 2630번 문제와 굉장히 유사한 문제이다.

ㆍ차이점은 단지 4조각으로 나누냐, 9조각으로 나누냐와 0, 1을 저장하느냐, -1, 0, 1을 저장하느냐의 차이였다.

ㆍ2630번 문제를 잘 이해하고 풀었다면, 이 문제는 정말 손쉽게 풀 수 있을 것이다.

코드

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

int arr[2187][2187];
int a = 0; // -1의 개수
int b = 0; // 0의 개수
int c = 0; // 1의 개수

void paper(int y, int x, int n) {
	int mark = arr[y][x];
	int flag = 0;
	for (int i = y; i < y + n; i++)
		for (int j = x; j < x + n; j++) {
			if (mark != arr[i][j]) {
				flag = 1;
				break;
			}
		}
	if (flag == 1) {
		// 종이를 9조각으로 나눈다
		paper(y, x, n / 3); 
		paper(y, x + n / 3, n / 3);
		paper(y, x + 2 * (n / 3), n / 3);
		paper(y + n / 3, x, n / 3);
		paper(y + n / 3, x + n / 3, n / 3);
		paper(y + n / 3, x + 2 * (n / 3), n / 3);
		paper(y + 2 *(n / 3), x, n / 3);
		paper(y + 2 * (n / 3), x + n / 3, n / 3);
		paper(y + 2 * (n / 3), x + 2 * (n / 3), n / 3);
	}
	else {
		if (mark == -1)
			a++;
		if (mark == 0)
			b++;
		if (mark == 1)
			c++;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	paper(0, 0, N);
	cout << a << '\n' << b << '\n' << c;
	return 0;
}