[ BOJ 백준 2339번 - 석판 자르기 ] 해설 및 코드

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

2339번: 석판 자르기

 

목적

석판을 자를 수 있는 여러 조건을 만족하여, 석판을 자를 수 있는 모든 경우의 수를 구하라. 다음은 석판을 자르는 한 가지의 예시이다.

 

접근법

1. 분할 정복 알고리즘으로 접근한다.

 

• 석판을 두개로 자른다. (가로로도 잘라보고, 세로로도 잘라본다.)
• 가로 방향으로 잘랐다면 석판은 위쪽, 아래쪽으로 구분이 될 것이다, (세로 방향으로 잘랐다면 왼쪽, 오른쪽으로... )
• 나뉜 두 개의 석판 각각을 또 두 개로 자른다. 이러한 방식으로, 잘라진 석판의 범위를 매개변수로 하는 재귀 함수를 구현한다.

2. 석판을 재귀적으로 자를 때, 석판 내부에 보석 결정체와 불순물의 개수에 따라 잘못 자른 경우인지, 제대로 자른 경우인지, 더 잘라볼 지로 나뉜다.

 

• 보석 결정체가 없거나,  보석 결정체가 1이고 불순물이 1개 이상이거나, 보석 결정체가 2개 이상이고 불순물이 없으면, 이 석판은 잘못 자른 경우이다.
• 보석 결정체가 1개이고 불순물이 없다면 제대로 자른 경우이다.
• 이 외의 경우는 판별하기 어려운 경우로, 더 잘라봐야 한다.

 

3. 더 잘라봐야 하는 경우에는 자를 수 있는지를 봐야한다. 우선, 자르고자 하는 방향에 맞게 모든 행이나 열을 경계선으로 삼는다. (가로로 자를 때는 하나의 행을, 세로로 자를 때는 하나의 열을...) 이때, 단 한가지 조건을 만족해야지 경계선을 경계삼아 석판을 자를 수 있는데, 바로 그 조건은 경계선에 1개 이상의 불순물만 있어야 한다는 것이다. 즉, 불순물이 하나도 없거나, 보석 결정체가 하나라도 있으면 경계선으로 삼아 자를 수 없다.

 

#include<iostream>
using namespace std;
 
int B[21][21][2];
 
int available(int s[2], int e[2]) {
    int cnt[3] = { 0, };
    for (int i = s[0]; i <= e[0]; ++i)
        for (int j = s[1]; j <= e[1]; ++j)
            ++cnt[B[i][j][0]];
 
    if (cnt[2] == 0)return 0;
    if (cnt[2] == 1) {
        if (cnt[1] == 0)return 1;
        else return 0;
    }
    if (cnt[1] == 0)return 0;
    return 2;
}
 
int cut(int s[2], int e[2], bool d) {
    int k = available(s, e);
    if (k == 0) return 0;
    if (k == 1) return 1;
 
    int ret = 0, first, second;
    for (int u = s[!d] + 1; u < e[!d]; ++u) {
        bool possible = false;
        for (int v = s[d]; v <= e[d]; ++v) {
            if (B[u][v][!d] == 2) {
                possible = false;
                break;
            }
            if (B[u][v][!d] == 1)possible = true;
        }
        if (!possible)continue;
 
        int tmp1[2][2] = { {e[0],u - 1},{u - 1,e[1]} };
        int tmp2[2][2] = { {s[0],u + 1},{u + 1,s[1]} };
 
        if ((first = cut(s, tmp1[d], !d)) == 0)continue;
        if ((second = cut(tmp2[d], e, !d)) == 0)continue;
 
        ret += (first * second);
    }
    return ret;
}
 
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {
        cin >> B[i][j][0];
        B[j][i][1] = B[i][j][0];
    }
 
    int s[] = { 0,0 }, e[] = { n - 1,n - 1 };
    int ans = cut(s, e, 1) + cut(s, e, 0);
 
    if (ans == 0)cout << -1;
    else cout << ans;
}