2339번 석판 자르기

문제 링크

석판 자르기

문제 풀이

불순물이 없고 보석이 한 개만 있을 경우 1을 반환하고, 보석이 없을 경우 0을 반환하는 것을 기저사례로 둔다. 그리고 불순물이 있을 때 가로나 세로 두 방법으로 자르는 경우 모두 센다. 줄을 자르려면 자르는 줄에 보석이 없어야 하므로 체크해준다. 그리고 나눈 뒤 재귀 호출을 하면 각각의 경우의 수가 나오는데 이들을 서로 곱한 값이 전체 경우의 수이다. 이를 모든 불순물에 대해 for문 돌려 수행한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int N, board[30][30];

bool isDivide(int start, int end, int fix, int dir) {
    if (dir == 0) {
        for (int k = start; k <= end; ++k)
            if (board[fix][k] == 2)
                return false;
    }
    else {
        for (int k = start; k <= end; ++k)
            if (board[k][fix] == 2)
                return false;
    }
    return true;
}

int solve(int y1, int x1, int y2, int x2, int dir) {
    int cnt[3] = { 0, };

    for (int i = y1; i <= y2; ++i) 
        for (int j = x1; j <= x2; ++j) 
            ++cnt[board[i][j]];

    if (cnt[2] == 1 && cnt[1] == 0) return 1;
    if (cnt[2] == 0) return 0;

    int ret = 0;
    for (int i = y1; i <= y2; ++i) {
        for (int j = x1; j <= x2; ++j) {
            if (board[i][j] == 1) {
                if (dir == 0 && isDivide(x1, x2, i, dir)) 
                    ret += solve(y1, x1, i - 1, x2, 1) * 
                            solve(i + 1, x1, y2, x2, 1);
                else if (dir == 1 && isDivide(y1, y2, j, dir))
                    ret += solve(y1, x1, y2, j - 1, 0) * 
                            solve(y1, j + 1, y2, x2, 0);
			}
		}
	}
    return ret;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> board[i][j];

    int ret = solve(0, 0, N - 1, N - 1, 0) + solve(0, 0, N - 1, N - 1, 1);

    cout << ((ret == 0) ? -1 : ret);
    return 0;
}