백준 알고리즘 풀이 1780번 - 종이의 개수

분할 정복 문제.

 

- 알고리즘 -

 

1. 각 종이에 있는 모든 칸의 수가 같은지를 확인한다.

2. 모든 칸의 수가 같다면 그 칸에 있는 숫자 인덱스 값 1더한다.

3. 모든 칸의 수가 같지 않다면, 종이에 있는 칸의 갯수를 1/3로 줄이고, 첫 칸을 각 종이의 첫번째 항으로 한다.

 

- 예외 조건 -

1. -1은 인덱스가 될 수 없으므로 값을 저장할 때 다 +1을 하고 넣어주어야 한다.

 

첫 칸을 각 종이의 첫번째 칸으로 하는게 좀 어려웠다. 간단히 생각해보면 for문을 두개 돌려서 넣으면 된다.

 

-소스 코드-

 

#include <iostream>
using namespace std;

int map[2188][2188];
int count[4]={0,};
bool check(int num,int x,int y)
{
	int isSame=true;
	for(int i=y;i<y+num;i++){
		for(int j=x;j<x+num;j++){
			if(map[i][j]!=map[y][x]){
				isSame=false;
				return isSame;	
			}
		}
	}
	return isSame;
}
// 종이의 모든 칸이 동일한지 동일하지 않은지 확인한다.

void seperate(int num, int x, int y)
{
	if(check(num,x,y)){ //종이의 모든 칸이 동일하다면 종이 그대로 사용
		count[map[y][x]+1]++; //-1은 인덱스에 올수 없으므로 모두 1을 더해준다. 예외조건
		return;
	}
	int m=num/3;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){ //나누는 과정
			seperate(m,x+j*m,y+i*m);//각 종이의 첫 칸을 첫칸으로 하고 다시 확인
		}
	}
}

int main()
{
	int num;
	cin>>num;
	for(int i=0;i<num;i++){
		for(int j=0;j<num;j++){
			cin>>map[i][j];
		}
	}
	seperate(num,0,0); // 맨 처음 종이는 제일 큰 종이 이므로 전체 종이의 맨 왼쪽 상단으로 
	for(int i=0;i<3;i++){
		cout<<count[i]<<endl;
	}
	return 0;
}