백준 2339

2339번: 석판 자르기



 

아이디어

1. 불순물을 기준으로 판을 잘라야 함. 모든 순서를 적용해서 잘라봐야 하는데, permutation으로 구현하면 (불순물 개수)!이 되므로 백트래킹으로 가지치기 해야함.

 

2. 판을 자를 수 있는지 판단하는 함수가 필요함. 판 크기에 따라 자를 수 있는 범위가 다르므로 왼쪽 위를 시작점, 오른쪽 아래를 끝점으로 변수를 받고 사이즈에 맞게 자름.

 

3. 잘린 판이 더 잘려야 되는지 판단하는 함수가 필요함.

 - 보석이 없으면 반드시 잘못된 판이니 더 잘라볼 필요가 없음. 0 리턴함.

 - 보석이 1개 있고 불순물이 없으면 제대로 잘린 판이니 1 리턴함.

 - 그 외는 더 잘라봐야 함.

 

4. 가능한 판의 경우의 수는 잘린 2판 각각의 경우의 수를 곱해서 구해야함.

 - 세로로 자른다 생각하고 왼쪽 판에 경우의 수가 2, 오른쪽 판의 경우의 수가 3이면 조합했을 때 총 6가지가 나옴.

 - 안 되는 판이 끼어있으면 0이 곱해져서 경우의 수에 포함 안 됨.

 

5. 처음 판을 자를 땐 가로, 세로 모두 자를 수 있으므로 함수 내에 구현하지 말고 main()에 구현하는 게 편리함.

 

 

구현

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

#define y first
#define x second
typedef long long ll;

int n;
int a[20][20];

bool cut(pair<int, int> s, pair<int, int> e, int it, bool col) {
    int zem = 0;
    if (col) {
        for (int i = s.y; i <= e.y; i++) {
            if (a[i][it] == 2) zem++;
        }
    }
    else {
        for (int j = s.x; j <= e.x; j++) {
            if (a[it][j] == 2) zem++;
        }
    }
    return zem > 0 ? false : true;
}

int possible(pair<int, int> s, pair<int, int> e) {
    int trash = 0;
    int zem = 0;
    for (int i = s.y; i <= e.y; i++) {
        for (int j = s.x; j <= e.x; j++) {
            if (a[i][j] == 1) trash++;
            else if (a[i][j] == 2) zem++;
        }
    }
    if (zem == 0) return 0;
    else if (zem == 1 && trash == 0) return 1;
    else return 2;
}

// dir 0이면 가로로 자르고 1이면 세로로 자름.
int solve(pair<int, int> s, pair<int, int> e, int dir) {
    int p = possible(s, e);
    if (p == 0 || p == 1) return p;

    int ans = 0;
    if (dir == 0) {
        for (int i = s.y; i <= e.y; i++) {
            for (int j = s.x; j <= e.x; j++) {
                if (a[i][j] != 1) continue;
                if (cut(s, e, i, 0)) {
                    ans += solve(s, {i - 1, e.x}, 1) * solve({i + 1, s.x}, e, 1);
                }
            }
        }
    }
    else {
        for (int i = s.y; i <= e.y; i++) {
            for (int j = s.x; j <= e.x; j++) {
                if (a[i][j] != 1) continue;
                if (cut(s, e, j, 1)) {
                    ans += solve(s, {e.y, j - 1}, 0) * solve({s.y, j + 1}, e, 0);
                }
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    
    pair<int, int> start = {0, 0}, end = {n - 1, n -1};
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] != 1) continue;
            if (cut(start, end, i, 0)) {
                ans += solve(start, {i - 1, end.x}, 1) * solve({i + 1, start.x}, end, 1);
            }
            if (cut(start, end, j, 1)) {
                ans += solve(start, {end.y, j - 1}, 0) * solve({start.y, j + 1}, end, 0);
            }
        }
    }
    if (ans == 0) cout << -1;
    else cout << ans;
    return 0;
}