백준 BOJ 2339 - 석판 자르기

분할정복 컷

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

2339번: 석판 자르기

보석 결정이 자르는 선 위에 위치하면 안된다는 조건을 놓쳐서

고민좀함.

선을 하나 그어주면 가로선인 경우로 예시를 들 때

선 윗부분의 직사각형 하나 ( 다음에 세로선을 그어야함 )

선 아랫부분의 직사각형 하나 ( 다음에 세로선을 그어야함 )

그래서 그어야할 선 방향을 매개변수로 하나 더 넣어주는 재귀함수를 짜면

분할정복이 됨.

 

모든 점에 대해서 가로세로로 선 그어서 쪼개는경우 다 생각해줘도

TLE는 안받았다.

 

재귀 탈출조건 생각하기가 좀 비직관적이라 느꼈는데

불순물이 없는 부분 직사각형은 분할정복의 가장 끝 노드? 에 해당하니까

반드시 보석 결정체가 "하나만" 있어야한다.

 

이게 아닌 경우는 불순물이 있으니까 쪼갤수 있을것.

쪼갠 뒤에 보석이 없던지말던지 그건 다음 재귀함수에서 알아서 빠져나올것이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int arr[23][23] = {0};

int recur(int x1, int y1, int x2, int y2, bool dir){
	
	//printf("[%d %d] to [%d %d]\n", x1,y1,x2,y2);
	
	int jewel = 0;
	int trash = 0;
	int ret = 0;
	
	vector<pair<int,int>> pos;
	
	for(int i=x1; i<=x2; i++){
		for(int j=y1; j<=y2; j++){
			if(arr[i][j] == 1){
				trash++;
				pos.push_back({i,j});
			}
			if(arr[i][j] == 2){
				jewel++;
			}
		}
	}
	
	if(trash == 0){
		if(jewel == 1) return 1;
		else           return 0;
	}
	
	for(auto k : pos){
		bool flag = true;
		if(dir){
			for(int i=y1; i<=y2; i++) if(arr[k.x][i] == 2) flag = false;
			if(flag) ret += recur(x1,y1,k.x-1,y2, !dir) * recur(k.x+1,y1,x2,y2, !dir);
		}
		else{
			for(int i=x1; i<=x2; i++) if(arr[i][k.y] == 2) flag = false;
			if(flag) ret += recur(x1,y1,x2,k.y-1, !dir) * recur(x1,k.y+1,x2,y2, !dir);
		}
	}
	return ret;
}

int main(){
	int n;
	cin >> n;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> arr[i][j];
		}
	}
	int ret = recur(0,0,n-1,n-1,0) + recur(0,0,n-1,n-1,1);
	if(ret == 0) cout << -1;
	else		 cout << ret;
	return 0;
}

코드가 좀 길긴 한데

그냥 간단히 설명해보자면 가로세로로 잘라줘야할 불순물 점을

vector<pair<int,int>> pos 에 저장하고

 

탈출조건 체크해준다음에

쪼개야할 경우에는 dir 매개변수 보고 방향 맞춰서 잘라줬다.

자를때 윗쪽/아래쪽 or 왼쪽/오른쪽은 서로 독립사건이니까 곱해주면 됨.

 

보석결정이 위로 올라가면 안되니까 bool flag 하나 만들고

자를 선 순회하면서 있는지 체크한번 해줬다.