[C++] 백준 2339번: 석판 자르기

🔗 문제

2339번: 석판 자르기

2339번: 석판 자르기

 

🖍 풀이

 

문제를 풀기 위해서는 총 3가지 과정을 정확히 이해해야 합니다.

1. 석판을 자를 수 있는 조건
2. 석판 자르기
3. 재귀적으로 석판 자르기 (내가 막혔던 부분)

 

석판을 자를 수 있는 조건

• 이전과 다른 방향으로 잘라야 한다. (가로, 세로의 반복)
• 자르고자 하는 열이나 행은 불순물을 포함한다.
• 자르고자 하는 열이나 행에 보석이 있으면 자를 수 없다.
• 잘랐을 때 반드시 석판이 2개로 나뉘어야 한다.

불순물을 모두 제거한 후 조각난 각각의 보드에는 보석이 1개만 있어야 한다.

 

석판 자르기

(r, c) (rr, cc) 범위의 석판을 (x, y)를 기준으로 잘랐을 때 어떻게 석판이 나뉠까?

 

 

↔️가로로 자른 경우

 

↕️세로로 자른 경우

 

재귀적로 석판 자르기

석판을 한번 잘랐다면 이제 불순물이 없을 때까지 계속 잘라 봅시다. 석판을 한 번 자르면 석판은 두 개가 됩니다. 자른 석판들이 ‘모두’ ‘잘’ 잘려야만 답에 추가할 수 있습니다. 잘린 석판 하나라도 보석이 두 개라던가 보석이 하나도 없다면 그 석판 자르기는 망한 겁니다! 이걸 재귀로 불렀을 때 어떻게 판단할까요?

 

바로 석판 잘 자르기 여부를 false, true로 반환하고 곱해주면 됩니다.

아래 처럼 잘린 두 조각의 석판에 대한 탐색을 하다가 어느 한 부분에서 조건에 맞지 않으면 return 0을 해줍니다. 이렇게 되면 다른 조각에서 조각을 잘 자르든 말든 결과값이 0이 되어 정답에 카운팅되지 않습니다. 

result += divided() * divided();

 

 

💾  소스

#include <iostream>

const int MAX = 21;

int N;
int board[MAX][MAX];

int isDone(int r, int c, int rr, int cc)
{
    int gems = 0;
    int impurities = 0;
    
    for(int i=r; i<=rr; ++i)
    {
        for(int j=c; j<=cc; ++j)
        {
            if(board[i][j] == 1)
            {
                impurities++;
            }
            else if(board[i][j] == 2)
            {
                gems++;
            }
        }
    }
   
    //잘린 보드에 불순물이 없고 보석이 하나면 더 이상 자를 필요가 없다.
   if(gems == 1 && impurities == 0)
       return true;
    if(gems < impurities)
        return 0;
    if(gems > 0 && impurities==0)
        return 0;
    
    return -1;
}

bool isBlocked(int r, int c, int rr, int cc, int idx, bool grain)
{
    if(grain)
    {
        for(int i=r; i<=rr; ++i)
        {
            if(board[i][idx] == 2)
                return true;
        }

    }
    else
    {
        for(int i=c; i<=cc; ++i)
        {
            if(board[idx][i] == 2)
                return true;
        }
    }
    
    return false;
}

int divided(int r, int c, int rr, int  cc, bool grain)
{
    // 석판을 다 잘랐는지 확인한다.
    if(isDone(r, c, rr, cc)==1)
        return 1;
    // 더 이상 진행해도 잘 자를 수 없다면 멈춘다.
    else if(isDone(r, c, rr, cc)==0)
        return 0;
        
    // 1. 불순물을 찾는다.
    // 2. 결에 맞게 자를 수 있는지 확인한다.
    // 3. 결에 맞게 잘라 결과를 result 에 저장한다.
    int result = 0;
    for(int i=r; i<=rr; ++i)
    {
        for(int j=c; j<=cc; ++j)
        {
            if(board[i][j] == 1)
            {
                if(grain)
                {
                    if(!isBlocked(r, c, rr, cc, i, false))
                    {
                        result += (divided(r, c, i-1, cc, false) * divided(i+1, c, rr, cc, false));
                    }
                }
                else
                {
                    if(!isBlocked(r, c, rr, cc, j, true))
                    {
                        result += (divided(r, c, rr, j-1, true) * divided(r, j+1, rr, cc, true));
                    }

                }
            }
        }
    }
    
    return result;

}

int main()
{
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
            std::cin >> board[i][j];
    }
    
    int answer = divided(0, 0, N, N, true) + divided(0, 0, N, N, false);
    std::cout << (answer > 0 ? answer : -1);
    
    return 0;
}