[백준 2339] 석판 자르기 (C++)

문제 설명

백준 2339번 문제는 주어진 석판에서 불순물과 보석을 포함한 부분을 자르는 방법의 수를 구하는 문제이다. 불순물(1)과 보석(2)이 섞여있는 석판을 잘라서 불순물이 없는 보석만을 포함하는 영역을 만들려고 한다. 단, 자르는 과정에서 불순물을 반드시 포함해야 하고, 자른 이후 영역에는 하나의 보석만 남아 있어야 한다.

문제 접근

해당 문제를 읽어보면 우리가 해결해야할 문제가 석판이 잘라질 때마다 두개로 나뉘어 작은 문제가 되는 것을 반복하는 것을 볼 수 있다. 문제가 작아지면서 반복 된다는 것은 재귀를 사용해야 한다는 것을 알 수 있으며, 두개로 나뉘어 진다는 것은 분할 정복에 해당하는 문제라는 것을 유추할 수 있다.

문제 풀이

전반적인 풀이방법은 현 상태의 석판이 자를 수 있는 모든 경우 이다. 이 말은 재귀적으로 문제를 풀 때, 기저 사례와 문제 분할을 아우러 설명한다.
예시를 들어 설명을 하겠다.

위 그림은 예제 입력1을 그림으로 표현한 것이다. 우리는 이 석판을 한번 잘라서 두개로 나눈다 했을 때, 어떻게 잘라야할까?

문제를 손으로 직접 풀어보면 이렇게 자르면서 시작해야 정답이 나오는 것을 알 수 있다. 하지만 컴퓨터로는 이것을 알고 자를 수가 없다. 즉, 우리는 현재 석판 상태에 대해서 자를 수 있는 모든 경우를 잘라서 다음 하위문제로 된 재귀에서 판단해야 한다는 것이다.

다음은 우리가 현재 석판에서 보석을 건들지 않고 불순물을 자를 수 있는 모든 경우의 수를 표시한 것이다. 위의 그림과 같이 현재 상태의 석판에서 자를 수 있는 모든 경우의 수를 자른다.


이렇게 자르다가 현재 석판이 불순물이 0개 이고, 보석이 1개 남았다면 1을 리턴하는 것이다. 하지만 만약에 잘못 자르게 된다면 어떻게 해야할까?

기본적으로 잘못 자르게 되면 해당 석판에 보석이 하나도 없게 되는 경우일 것이다. 하지만 이런 기저 사례를 짜게 된다고 치면 결국 보석이 하나도 남지 않게 될 때까지 재귀를 호출해야하며 이것은 재귀 호출의 대부분의 시간을 차지하는 호출 부분에서 많은 해저드를 발생하게 될 것이다.

이런 불필요한 호출을 줄이기 위해 우리는 보석이 1개가 되기전에 이것이 잘못 잘렸다는 것을 미리 판단 할 수 있을까? 그에 대해 간단한 아이디어로 가능하다. 현재 석판에서 보석들이 각 조각에 반드시 하나가 존재하게 하려면 (보석의 개수 - 1) == ( 불순물의 개수 ) 가 되어야 한다.

이러한 사실을 가지고 해당 문제의 알고리즘을 정리해본다.

알고리즘 설명

1. 기저 사례 (Base Cases)

• 자르기 불가능한 경우: (보석의 개수-1) != (불순물의 개수)인 경우, 0을 반환
• 보석이 하나만 남은 경우: 해당 영역에 보석이 하나만 존재하고 불순물이 없다면, 1을 반환

2. 재귀적 분할 (Recursive Case)

• 가로로 자르기:
  1. 이전에 세로로 잘랐다면, 가로로 자르기
  2. 각 불순물의 y 좌표(가로)를 확인하고, 해당 좌표에 보석이 없으면 그 지점을 기준으로 가로로 자른다
  3. 자른 두 조각에 대해 재귀적으로 func를 호출
• 세로로 자르기:
  1. 이전에 가로로 잘랐다면, 세로로 자르기
  2. 각 불순물의 x 좌표(세로)를 확인하고, 해당 좌표에 보석이 없으면 그 지점을 기준으로 세로로 자른다
  3. 자른 두 조각에 대해 재귀적으로 func를 호출
• 초기 상태: 가로, 세로 모두 자른다

3. 최종 결과 합산

• 각각의 자르기 방법에서 얻어진 결과들을 모두 합산하여 최종적으로 가능한 경우의 수를 도출

코드

#include "bits/stdc++.h"

using namespace std;

int seq[20][20];

// 주어진 석판 영역을 가로 또는 세로로 자를 수 있는 방법의 수를 재귀적으로 계산하는 함수
// y1, y2: 현재 영역의 시작과 끝 y좌표
// x1, x2: 현재 영역의 시작과 끝 x좌표
// d: 이전에 자른 방향 (0: 가로, 1: 세로, -1: 처음 자르기)
int func(int y1, int y2, int x1, int x2, int d)
{
    int star = 0;  // 현재 영역의 별(2)의 개수
    int dust = 0;  // 현재 영역의 불순물(1)의 개수

    vector<int> yStarCoordi;  // 별의 y좌표를 저장하는 벡터
    vector<int> xStarCoordi;  // 별의 x좌표를 저장하는 벡터

    vector<int> yDustCoordi;  // 불순물의 y좌표를 저장하는 벡터
    vector<int> xDustCoordi;  // 불순물의 x좌표를 저장하는 벡터

    // 현재 영역에서 별과 불순물의 좌표를 기록하고 개수를 센다
    for (int i = y1; i < y2; i++)
    {
        for (int j = x1; j < x2; j++)
        {
            if (seq[i][j] == 2)
            {
                yStarCoordi.push_back(i);
                xStarCoordi.push_back(j);
                star++;
            }

            if (seq[i][j] == 1)
            {
                yDustCoordi.push_back(i);
                xDustCoordi.push_back(j);
                dust++;
            }
        }
    }

    // 기저 사례 1: 나눌 수 없는 경우, 0을 반환
    if ((star - 1) - dust != 0)
        return 0;

    // 기저 사례 2: 이미 완성된 경우, 1을 반환
    if (dust == 0 && star == 1)
        return 1;

    int ret = 0;  // 가능한 자르기 방법의 수를 저장하는 변수

    // 이전에 가로로 자르지 않았다면, 가로로 자르기를 시도
    if (d != 0)
    {
        for (int i = 0; i < yDustCoordi.size(); i++)
        {
            int isStar = 0;
            for (int j = 0; j < yStarCoordi.size(); j++)
            {
                if (yDustCoordi[i] == yStarCoordi[j])
                {
                    isStar = 1;
                    break;
                }
            }
            // 같은 y좌표에 별이 없다면 가로로 자르고, 결과를 재귀적으로 계산
            if (!isStar)
            {
                ret += func(y1, yDustCoordi[i], x1, x2, 0) * func(yDustCoordi[i] + 1, y2, x1, x2, 0);
            }
        }
    }

    // 이전에 세로로 자르지 않았다면, 세로로 자르기를 시도
    if (d != 1)
    {
        for (int i = 0; i < xDustCoordi.size(); i++)
        {
            int isStar = 0;
            for (int j = 0; j < xStarCoordi.size(); j++)
            {
                if (xDustCoordi[i] == xStarCoordi[j])
                {
                    isStar = 1;
                    break;
                }
            }
            // 같은 x좌표에 별이 없다면 세로로 자르고, 결과를 재귀적으로 계산
            if (!isStar)
            {
                ret += func(y1, y2, x1, xDustCoordi[i], 1) * func(y1, y2, xDustCoordi[i] + 1, x2, 1);
            }
        }
    }

    return ret;  // 현재 영역에서 가능한 자르기 방법의 수를 반환
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(0);  // 입출력 속도 향상
    cin.tie(0);  // 입력과 출력을 비동기적으로 처리하지 않음

    int n;  // 석판의 크기 (n x n)
    cin >> n;

    // 석판의 상태를 입력받아 배열에 저장
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> seq[i][j];
        }
    }

    // 전체 석판에 대해 자르기 함수를 호출하여 가능한 방법의 수 계산
    int ret = func(0, n, 0, n, -1);

    // 결과가 0이면 자르기 불가능하므로 -1을 출력, 그렇지 않으면 가능한 방법의 수 출력
    if (ret == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ret << endl;
    }
    return 0;
}