[백준] 2630번: 색종이 만들기 (C++)

 

문제

---

문제 링크: https://noj.am/2630

2630번: 색종이 만들기

 

문제 분석

---

제목이 색종이 만들기?

 

색종이로 무언가를 만든다는 건가?

아니면 색종이 그 자체를 만든다는 걸까?

 

색종이로 뭘 만들긴 개뿔을 만들어

 

읽어보니깐 그냥 큰 종이를 작은 종이들로 나누는 거였다

글도 길고, 무슨 표같은 것도 있지만 쉽고 간단하게 알려주겠다.

 

우선 색도 두 개밖에 없으니 색종이는 무슨, 그냥 타일이라 생각하자.

 

그리고 지금 당신은 부모님한테 혼나는 중이다.

시선은 바닥을 보면서 바닥 타일의 패턴을 분석하고 있다..

 

가끔 중간에 강아지 닮은 모양도 있음

혼날 때 바닥이나 벽보면서 타일 분석 국룰임

 

아무튼 보다보니, 바닥 타일이 이상하게 나눠져있다.

당신은 정사각형 형태인 타일들을 기준으로 색상 별로 구분짓기로 했다.

그리고 지금 그것들이 각각 몇 개인지 세보는 중이다.

 

색상 별 정사각형 타일의 개수를 출력하는 게 문제다.

 

 

처음 1면에 다른 색이 하나라도 섞여 있다면 4등분 해준다.

그리고 4개로 나눠진 부분들에서 모두 같은 색으로 구성됐는지 확인한다.

 

같으면 카운트해주고, 아니라면 또 4등분한다.

이 과정을 모든 부분의 확인이 끝날 때까지 반복한다.

 

필요한 것 목록.

1.  해당 부분의 면이 모두 같은 색인지 확인하는 함수.

2.  같은 색이면 카운트하고, 아니면 4등분하는 함수.

 

이제 4등분을 계속 반복하게 된다는 것을 알았을 것이다.

이번엔 별 다른 라이브러리는 필요없고 재귀를 이용해 분할 정복할 것이다.

분할 정복: 큰 문제를 작게 쪼개 풀어내는 것

 

 

자세한 풀이

---

 

솔직히 같은 색인지 확인하는 함수는

변 길이만큼 이중 반복돌며 확인하면되니 간단하고,

길이랑 시작 좌표만 잘 넘겨주면 되잖아.

 

따라서, 같으면 카운트하고 다르면 4등분하는 함수가 핵심이다.

행/열이 좀 헷갈릴 수 있는데 익숙하지 않다면,

이렇게 그림으로 그려보자.

 

위의 확인 함수의 결과로 조건을 나눠,

결국 4등분하게 된다면 각 시작점은 저렇게 될 것이다.

 

이게 뭔가 문제 Z랑도 느낌이 비슷하다고 할 수 있다.

오른쪽으로 가거나 내려갈수록 행 또는 열의 좌표가 증가한다.

 

얼마만큼 증가하는지는 전체 변의 길이가 N이라고 한다면,

N/2만큼 증가하는 게 보이는가?

 

기존 좌표에서 증가한만큼 더해주고 넘겨주면 된다.

4등분한 것이니까, 각각의 상황에 맞게 4번 실행해주면 되겠지?

for(int i = 0; i < 2; i++) // 4분할 - 각 사각형 시작 부분. 
	for(int j = 0; j < 2; j++)
		paper(n / 2, x + n / 2 * i , y + n / 2 * j);
		// 변은 절반씩 감소, 최초 x y에서 살 붙이기.

 

[그대로][그대로] / [그대로][증가] / [증가][그대로] / [증가][증가]의 패턴을

반복문을 이용하면 간략하게 나타낼 수 있다.

 

 

하지만 정말 그렇게 잘 나눠져 인식되었을까?

바로 확인해보자!

#include <bits/stdc++.h>
using namespace std;

int N;
bool board[129][129];
bool draw[129][129]; // 테스트용. 
int white, blue;

bool check(int n, int x, int y){ // 같은 색상인지 판별. 
	for(int i=x;i<x+n;i++)
		for(int j=y;j<y+n;j++)
			if(board[i][j]!=board[x][y]) return 0;
	return 1;
}

void paper(int n, int x, int y){ // 하양 or 파랑. 
	if(check(n,x,y)){
		for(int i=x;i<x+n;i++) // 인식한 영역 draw에 표시. 
			for(int j=y;j<y+n;j++)
				draw[i][j]=board[x][y];
			
		if(!board[x][y])white++;
		else blue++;
		return;
	}
	
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			paper(n/2,x+n/2*i,y+n/2*j);
			// 변은 절반씩 줄어들고, 최초 x y에서 증가되는 유형. 
}

int main(){	
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> N;
	
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			cin >> board[i][j];
	
	paper(N,0,0);
	
	cout << "\n인식한 색종이 확인)\n";	
	for(int i=0;i<N;i++,cout<<'\n')
		for(int j=0;j<N;j++)
			cout << draw[i][j] << ' ';
	cout << '\n';
				
	cout << white << '\n' << blue;
}

잘 나눠져 인식되어 들어갔음을 알 수 있다.

 

 

재귀 팁

---

아 그리고 재귀가 익숙하지 않거나 어렵다는 분들을 위한 팁.

나중에 알고리즘 포스팅에도 올리겠지만 그건 그때 또 참고해주고,

 

재귀의 과정에 대해서 순서대로 의식의 흐름을 맡기면 너무 어려워진다.

순차지향적인 사고가 재귀 코드를 짜지 못하게 방해할 거다.

 

그냥 첫 번째 공통 문제의 flow만 그대로 적용시키고,

탈출 구문 / 기저 조건(base case)만 잘 정의하면 우리의 역할은 그걸로 끝이다.

 

곁에서 요정이 우리를 도와주고 있다고 생각하란 말이야

우리 눈에 보이지 않는 재귀의 요정이 해결해 줄 것이다.

우리 인간의 역할은 문제 파악, 정의가 끝이고

깊고 자세하게 들어가서 계산/처리해주는 건 요정이 알아서 해준다.

고 생각하자

 

 

의심하지 말고 그냥 믿어!!!!@ 확 그냥

그럼 맘이 편해질테니까

 

 

코드 (C++)

---

#include <bits/stdc++.h>
using namespace std;

int N;
bool board[129][129];
int white, blue;

bool check(int n, int x, int y){ // 모두 같은 색인지 판별.
	for(int i=x;i<x+n;i++)
		for(int j=y;j<y+n;j++)
			if(board[i][j]!=board[x][y]) return 0;
	return 1;
}

void paper(int n, int x, int y){ // 증가 or 분할. 
	if(check(n,x,y)){
		if(!board[x][y])white++;
		else blue++;
		return;
	}
	
	for(int i=0;i<2;i++) // 4분할 / 각 사각형 시작 부분. 
		for(int j=0;j<2;j++)
			paper(n/2,x+n/2*i,y+n/2*j);
			// 변은 절반씩 감소, 최초 x y에서 살 붙이기. 
}

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

궁금한 부분은 댓글 남겨주세요