백준 2339 석판자르기

jathazp·2021년 5월 25일

분할정복 알고리즘

algorithm

목록 보기

38/57

문제링크

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

문제

풀이

분할정복 + 구현력이 필요한 문제이다.

for 문으로 map을 돌면서 불순물이 있는 인덱스에서 분할정복으로 가로와 세로로 잘라가면서 풀어주었다.

이때 자르는 방법은 따로 인덱스에 표시하지 않고 자른 석판의 왼쪽 위, 오른쪽 아래 좌표를 넘기며 불순물이 섞여 있는지 체크하며 진행했다.

잘린 석판에 불순물이 더 섞이지 않았고 보석이 하나만 포함되어있으면 1을 리턴하였고 아니면 0을 리턴하였다.

매번 자를때 두 개의 석판이 생겨나므로 두석판에서 가능한 경우의 수를 리턴 받고 그 수를 곱한 값을 t_ans에 더해주었다.

map을 돌고 난 후 t_ans의 값을 리턴하면 해당 석판에서 가능한 경우의 수를 리턴하게 된다.

코드

#include <iostream>
using namespace std;
int n;
int maps[21][21];

bool check(int x, int y, int to_x, int to_y) {

	bool treasure = false;
	for (int i = x; i <= to_x; i++) {
		for (int j = y; j <= to_y; j++) {
			if (maps[i][j] == 2) {
				if (treasure) return false;
				treasure = true;
			}
		}
	}

	if (!treasure) return false;
	return true;

}

bool can_cut(int x, int y, int to_x, int to_y, int target, int dir) {
	bool chcek = true;
	if (dir == 0) {
		for (int i = y; i <= to_y; i++) {
			if (maps[target][i] == 2) return false;
		}
	}
	else if (dir == 1) {
		for (int i = x; i <= to_x; i++) {
			if (maps[i][target] == 2) return false;
		}
	}

	return true;
}

int solve(int x, int y, int to_x, int to_y, int before_dir) {

	if (check(x, y, to_x, to_y)) return 1;

	int t_ans = 0;
	for (int i = x; i <= to_x; i++) {
		for (int j = y; j <= to_y; j++) {
			if (maps[i][j] == 1) {
				int t1 = 0, t2 = 0;
				if (before_dir == 0) {
					if (can_cut(x, y, to_x, to_y, j, 1)) {
						t1 = solve(x, y, to_x, j - 1, 1);
						t2 = solve(x, j + 1, to_x, to_y, 1);
					}
				}
				else {
					if (can_cut(x, y, to_x, to_y, i, 0)) {
						t1 = solve(x, y, i - 1, to_y, 0);
						t2 = solve(i + 1, y, to_x, to_y, 0);
					}
				}
				t_ans += t1 * t2;
			}
		}
	}

	return t_ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maps[i][j];
		}
	}

	int ans = 0;
	ans += solve(0, 0, n - 1, n - 1, 0);
	ans += solve(0, 0, n - 1, n - 1, 1);

	if (ans == 0) cout << -1;
	else cout << ans;


}