[ 백준 14391 ] 종이 조각 (C++)

백준의 종이조각(14391) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 접근하는 방법이 생각보다 어려웠던 문제였던 것 같다. 본인은 자를 수 있는 모든 가로방향과 세로방향으로 다 짤라보면서

   최대값을 찾는 방식인 '완전탐색'을 이용해서 구현해보았다.

   문제를 구현하는 순서를 설명하자면 다음과 같다.

   1. 시작점을 찾는다. (아직 잘리지 않는 점을 찾는다는 의미)

   2. 그 점에서 가로로 자를 수 있는 최대 크기를 찾는다.

   3. 가로로 자를 수 있는 최대크기에서 최소크기까지 반복하면서 자른다.

   4. 그 점에서 세로로 자를 수 있는 최대 크기를 찾는다.

   5. 세로로 자를 수 있는 최대크기에서 최소크기 까지 반복하면서 자른다.

   일단 간략하게 적어보자면 위와 같다. 구체적으로 코드로 어떻게 구현을 하는지 코드와 함께 상세하게 알아보자.

1. 시작점을 찾는다. (아직 잘리지 않은 점을 찾는다는 의미) (본문 함수 : Find_Point())

- 위 과정은 지금까지 자른점을 제외한 남은 점들 중에서 가장 빠른 점을 찾는 다는 것을 의미한다.

  본인은 이미 '잘랐다' 라는 것을 표시해주기 위해서 Visit[][] 2차원 배열을 사용해주었다.

  Visit[a][b] = true 의 의미는 (a,b)는 이미 특정 기준으로 잘린 좌표이기 때문에 건들지 마세요. 라는 것을 의미한다.

  이 부분을 코드로 보면 다음과 같다.

pair<int,int> Find_Point()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Visit[i][j] == false) return{ i, j };    // 자르지 않은 가장 빠른점
        }
    }
    return{ -1, -1 };    // 모든 점을 다 잘랐을 경우 { -1, -1 } 을 return
}

2 & 4. 그 점에서 가로 or 세로로 자를 수 있는 최대 크기를 찾는다. (본문 함수 : Find_Max_Size(int, int, char))

- 본인은 가로로 먼저 다 잘라본 후, 세로로 자르는 순서로 했기 때문에 위 과정이 2번이고, 세로로 자르는 것이 4번

  과정이 되었다. 이 두 과정이 순서가 바뀌어도 상관은 없다.

  가로로 자르는 경우에는, 현재 점부터 M까지 진행하면서 아직 자르지 않은 점이 있을 때마다 Count해주어서 몇 칸까지

  한번에 묶을 수 있는지를 계산해서 return 해준다. 코드는 다음과 같다.

int Find_Max_Size(int x, int y, char C)    // C = 'G'이면 가로, C = 'S' 이면 세로로 자른다는 것을 의미.
{
    int R_Value = 0;
    if (C == 'G')
    {
        for (int i = y; i < M; i++)    // 현재 좌표에서 부터 맵의 가로길이의 최대까지 반복하면서
        {
            if (Visit[x][i] == false) R_Value++;    // 묶을 수 있는 범위라면 ++
            else break;
        }
    }
    else                        // 세로의 경우
    {
        for (int i = x; i < N; i++)    // 맵의 세로길이의 최대까지 반복
        {
            if (Visit[i][y] == false) R_Value++;
            else break;
        }
    }
    return R_Value;
}

남은 과정이 3번 5번 과정인데, 이 과정은 최대크기에서 최소크기까지 반복한다는 것을 나타낸 것이다.

이 부분이 하는 일이... 예를 들어서 맵의 크기가 4x4 짜리인데, (0, 0)에 있다고 생각해보자.

(0, 0)에서 가로로 자른다고 가정하면, 총 4방법으로 자를 수 있다.

(0, 0) 하나만 자르는 방법, (0, 0) ~ (0, 1) 2개를 하나로 자르는 방법, (0, 0) ~ (0, 2) 3개를 하나로 자르는 방법,

(0, 0) ~ (0, 4) 4개를 하나로 자르는 방법. 이렇게 총 4가지 방법이 있다. 이 4가지 방법으로 자르는 것을 3, 5번에서

진행되게 된다.

이 외에도 완성된 코드를 보면 알 수 있겠지만, 이미 자른 좌표들에 대해서는 Visit[][] 배열에 대한 Check가 반드시

필요하고, 중간중간 계산을 해주면서 재귀호출을 해주었다.

가장 중요한 재귀함수의 매개변수가 의미하는 것은, 현재까지 계산된 값을 의미한다.

이 재귀함수의 종료조건은 1번에서 시작점을 { -1, -1 } 로 return받는 순간, 기존의 값과 비교하면서 값을 갱신하고

종료하게 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<string>
 
#define endl "\n"
#define MAX 4
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int Select[16];
bool Visit[MAX][MAX];
vector<int> V;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j] - '0';
        }
    }
}
 
pair<int,int> Find_Point()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Visit[i][j] == false) return{ i, j };
        }
    }
    return{ -1, -1 };
}
 
int Find_Max_Size(int x, int y, char C)
{
    int R_Value = 0;
    if (C == 'G')
    {
        for (int i = y; i < M; i++)
        {
            if (Visit[x][i] == false) R_Value++;
            else break;
        }
    }
    else
    {
        for (int i = x; i < N; i++)
        {
            if (Visit[i][y] == false) R_Value++;
            else break;
        }
    }
    return R_Value;
}
 
void Make_Visit(int x, int y, int Size, char C, bool T)
{
    if (C == 'G')
    {
        for (int i = y; i < y + Size; i++)
        {
            Visit[x][i] = T;
        }
    }
    else
    {
        for (int i = x; i < x + Size; i++)
        {
            Visit[i][y] = T;
        }
    }
}
 
int Calculate(int x, int y, int Size, char C)
{
    int R_Value = 0;
    
    if (C == 'G')
    {
        for (int i = y; i < y + Size; i++)
        {
            R_Value = R_Value + MAP[x][i];
            R_Value = R_Value * 10;
        }
    }
    else
    {
        for (int i = x; i < x + Size; i++)
        {
            R_Value = R_Value + MAP[i][y];
            R_Value = R_Value * 10;
        }
    }
    R_Value = R_Value / 10;
    return R_Value;
}
 
void DFS(int Total)
{
    pair<int, int> Pos = Find_Point();
    int x = Pos.first;
    int y = Pos.second;
    
    if (x == -1 && y == -1)
    {
        if (Answer < Total) Answer = Total;
        return; 
    }
 
    int Size = Find_Max_Size(x, y, 'G');
    for (int S = Size; S > 0; S--)
    {
        Make_Visit(x, y, S, 'G', true);
        int Temp = Calculate(x, y, S, 'G');
        DFS(Total + Temp);        
        Make_Visit(x, y, S, 'G', false);
    }
    
    Size = Find_Max_Size(x, y, 'S');
    for (int S = Size; S > 0; S--)
    {
        Make_Visit(x, y, S, 'S', true);
        int Temp = Calculate(x, y, S, 'S');
        DFS(Total + Temp);
        Make_Visit(x, y, S, 'S', false);
    }
}
 
void Solution()
{
    if (N == 1 && M == 1)
    {
        cout << MAP[0][0] << endl;
        return;
    }
    
    DFS(0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}