[ 백준 14500 ] 테트로미노 (C++)

백준의 테트로미노(14500) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 맵의 크기와 맵이 입력으로 주어진다. 맵은 정수형 숫자로 이루어져 있다.

- 도형 5개가 주어진다. 5개의 도형은 회전시킬수도 대칭시킬수도 있다. (도형의 모양은 문제참고)

- 위에서 말한 5개의 도형을 맵에 넣었을 때 최댓값을 구하는 것이다.

[ 문제풀이 ]

1. 일단 정말 완전탐색에 의미에 입각해서 모든 도형을 회전시킬 수 있는 모든방향으로 회전시킨 모형과, 대칭시킬 수 있는

   모든 방향으로 대칭시킨 모형을 하나하나 다 대입해서 풀어도 답이 나온다고 한다.

2. 나는 처음에 잘 모르겠어서 1)번 방식으로 하다가 포기했다.

3. 그런데 모형들을 잘보면 공통점을 하나 발견할 수 있다. 바로 Depth = 3 이라는 것이다.

  그림에서 표시한 것 처럼 0번을 시작점으로 가정해보자.

    하늘색 모양의 긴 막대기 모양을 어떻게 회전한다 하더라도, DFS의 Depth 혹은 BFS의 Level을 계산해보면 내가 표시해

    놓은 것처럼 숫자가 새겨질 것이다. 옆에 노랑색 사각형을 포함한 모든 도형들이 조금만 생각해보면 내가 말한대로

    Depth가 3 혹은 Level이 3인 구간에서 멈출 것이다. 하지만 보라색 ㅜ 모양인 이 도형은 그렇지 않다. 시작점을 어떻게

    잡더라도 절대로 Depth가 3에서 끝날 수가 없는 모양이다.

4. 3)에서 모든 것을 다 설명하였다. 본인은 이 문제를 DFS로 해결하였는데, 모든 정점에서 DFS를 계산하였다.

   적절한 범위 내에 있는 좌표에 대해서는 매개변수로 계속해서 DFS를 재귀호출 하였으며, Depth가 3인 경우에 숫자들의

   총합을 구하는 계산만 하고 끝내는 식으로 구현하였다. 문제가 엄청나게 어려워보이는데, Depth가 3이 된다라는 것만

   파악한다면 어렵지 않은 문제이다.

   (참고로 DFS의 매개변수는 (x, y, Sum, Cnt) 4개를 설정해주었다.)

5. 4)에서 구현했다고 끝나는 것이 아니다. 앞서 말했듯이 ㅜ 모양은 Depth가 3이 나오지 않는 특별한 도형이기 때문에 따로

   계산을 해줘야 한다. 본인은 ㅗ/ㅜ/ㅏ/ㅓ 이 4가지 모양에 대해서 범위를 파악하면서 모든 정점에서 모두 계산해 주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 500
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y, int Sum, int Cnt)
{
    Visit[x][y] = true;
 
    if (Cnt == 3)
    {
        Answer = Bigger(Answer, Sum);
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (Visit[nx][ny] == true) continue;
 
        DFS(nx, ny, Sum + MAP[nx][ny], Cnt + 1);
        Visit[nx][ny] = false;
    }
}
 
void Shape1(int x, int y)
{
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x - 1][y + 1];
    if (Tmp_Sum > Answer) Answer = Tmp_Sum;
}
 
void Shape2(int x, int y)
{
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x + 1][y + 1];
    if (Tmp_Sum > Answer) Answer = Tmp_Sum;
}
 
void Shape3(int x, int y)
{
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 2][y] + MAP[x + 1][y + 1];
    if (Tmp_Sum > Answer) Answer = Tmp_Sum;
}
 
void Shape4(int x, int y)
{
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x - 1][y + 1] + MAP[x][y + 1] + MAP[x + 1][y + 1];
    if (Tmp_Sum > Answer) Answer = Tmp_Sum;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            memset(Visit, false, sizeof(Visit));
            DFS(i, j, MAP[i][j], 0);
            if (i - 1 >= 0 && j + 2 < M) Shape1(i, j);
            if (j + 2 < M && i + 1 < N) Shape2(i, j);
            if (i + 2 < N && j + 1 < M) Shape3(i, j);
            if (i + 1 < N && i - 1 >= 0 && j + 1 < M) Shape4(i, j);
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}