[ 백준 4920 ] 테트리스 게임 (C++)

백준의 테트리스 게임(4920) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 백준의 테트로미노(14500) 와 비슷한 문제 같지만 만들 수 있는 도형의 모양이 다르다는 점에서 차이가 존재하는 문제이다.

   먼저, 문제에서 주어진 도형들 중에서 나올 수 없는 도형들이 뭐가 있는지 알아보자.

   모든 테트리스 블록은 90도 회전시킬 수 있고, 일부 조각은 4가지 형태를 가질 수 있다고 했다.

   즉, 도형을 90도, 180도, 270도, 360도 회전시킨 총 4가지의 형태를 가질 수 있다는 말이다.  

   이렇게 생긴 블록에 주목해보자. 이 블록은 90도, 180도, 270도, 360도 회전시키면 나올 수 있는 블록은

   다음과 같다.

  

    그렇다면 다음과 같은 모양들은 나올 수 있을까 ??

  

    이 도형들은 절대로 나올 수가 없다. 왜냐하면, 주어진 5조각 중에서 어떤 조각을 90도로 회전시켜도 위와 같은 형태를

    만들 수 없기 때문이다. 즉, 우리가 하는 테트리스 게임과 달리 나올 수 없는 모양이 존재한다는 것에 대해 헷갈리지 말자.

2) 본격적인 구현에 들어가보자. 본인은 맵을 (0, 0)부터 (N - 1, N - 1) 까지 탐색하면서, 도형 5개의 4가지 모양들이

   들어갈 수 있는지 범위만 체크해주면서 하나하나 다 넣어서 합을 계산해 보았다.

   이 과정은... 말로 설명하는것 보다는 코드를 보는 것이 훨씬 이해가 쉬울 것이다.

   코드에 대해서 설명을 하자면 

   

   본인은 이렇게 도형들에 번호를 붙였으며, 각 도형들이 들어갈 수 있는 좌표라면

   Shape'x'(x, y, Num) 의 식으로 함수를 호출해주었다.

   Shape함수는 총, Shape1, Shape2, Shape3, Shape4, Shape5 5가지 모양에 대해서 개별적으로 구현하였으며

   뒤에 매개변수의 의미는, (x, y) 는 현재 좌표점을 의미하고, 3번째 매개변수인 Num은, 모양을 의미한다.

   1번 도형같은 경우에는 0과, 1 2가지의 모양을 가질 수 있으므로, Shape1(x,y,0), Shape1(x,y,1) 이런식으로 2번

   호출하였으며, 3번 도형같은 경우 총 4가지 모양을 가질 수 있으므로 Shape3(x,y,0~3) 이렇게 총 4번을

   호출해서 합을 계산해 주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    Answer = -987654321;
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Shape1(int x, int y, int S)    
{
    // 1번 도형 '|' 도형(2가지 형태로 존재가능)
 
    int Temp_Sum = 0;
    if (S == 0) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x][y + 3];
    else if (S == 1) Temp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 2][y] + MAP[x + 3][y];
 
    if (Temp_Sum > Answer) Answer = Temp_Sum;
}
 
void Shape2(int x, int y, int S)    
{
    // 2번 도형 'Z'와 비슷한 도형(2가지 형태로 존재가능)
 
    int Temp_Sum = 0;
    if (S == 0) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x + 1][y + 1] + MAP[x + 1][y + 2];
    else if (S == 1) Temp_Sum = MAP[x][y + 1] + MAP[x + 1][y + 1] + MAP[x + 1][y] + MAP[x + 2][y];
 
    if (Temp_Sum > Answer) Answer = Temp_Sum;
}
 
void Shape3(int x, int y, int S)
{
    // 3번 도형 'ㄱ'과 비슷한 도형(4가지 형태로 존재가능)
    int Temp_Sum = 0;
    if (S == 0) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x + 1][y + 2];
    else if (S == 1) Temp_Sum = MAP[x + 2][y] + MAP[x][y + 1] + MAP[x + 1][y + 1] + MAP[x + 2][y + 1];
    else if (S == 2) Temp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 1][y + 1] + MAP[x + 1][y + 2];
    else if (S == 3) Temp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 2][y] + MAP[x][y + 1];
 
    if (Temp_Sum > Answer) Answer = Temp_Sum;
}
 
void Shape4(int x, int y, int S)
{
    // 4번 도형 'ㅜ'와 비슷한 도형(4가지 형태로 존재가능)
    int Temp_Sum = 0;
 
    if (S == 0) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x - 1][y + 1];
    else if (S == 1) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x + 1][y + 1];
    else if (S == 2) Temp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 2][y] + MAP[x + 1][y + 1];
    else if (S == 3) Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x - 1][y + 1] + MAP[x + 1][y + 1];
 
    if (Temp_Sum > Answer) Answer = Temp_Sum;
}
 
void Shape5(int x, int y)
{
    // 2x2짜리 정사각형의 형태를 가진 도형(1가지 형태로 존재가능)
    int Temp_Sum = 0;
    Temp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x + 1][y] + MAP[x + 1][y + 1];
 
    if (Temp_Sum > Answer) Answer = Temp_Sum;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (j + 3 < N) Shape1(i, j, 0);
            if (i + 3 < N) Shape1(i, j, 1);
 
            if (i + 1 < N && j + 2 < N) Shape2(i, j, 0);
            if (i + 2 < N && j + 1 < N) Shape2(i, j, 1);
 
            if (i + 1 < N && j + 2 < N)
            {
                Shape3(i, j, 0);
                Shape3(i, j, 2);
            }
            if (i + 2 < N && j + 1 < N)
            {
                Shape3(i, j, 1);
                Shape3(i, j, 3);
            }
 
            if (i - 1 >= 0 && j + 2 < N) Shape4(i, j, 0);
            if (i + 1 < N && j + 2 < N) Shape4(i, j, 1);
            if (i + 2 < N && j + 1 < N) Shape4(i, j, 2);
            if (i + 1 < N && i - 1 >= 0 && j + 1 < N) Shape4(i, j, 3);
 
            if (i + 1 < N && j + 1 < N) Shape5(i, j);
        }
    }
}
 
void Solve()
{
    for (int Tc = 1; ; Tc++)
    {
        cin >> N; 
        if (N == 0) break;
 
        Initialize();
        Input();
        Solution();        
 
        cout << Tc << ". " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}