[ 백준 19235 ] 모노미노도미노 (C++)

백준의 모노미노도미노(19235) 문제이다.

[ 문제 바로가기 ]

(설명이 굉장히 길어요 !)

[ 문제풀이 ]

조금은 특이한 모양으로 생긴 맵에서 도형을 움직이고 제거해주는 내용을 구현해야 하는 문제이다.

먼저, 주어진 맵을 어떻게 관리할지 어떻게 구현할지에 대해서 부터 이야기하고 본격적인 구현으로 넘어가보자.

1. 맵 관리

먼저 특이하게 생긴 맵을 어떻게 처리할지에 대해서부터 알아보자.

.

맵이 위와 같은 형태로 구현되어 있는데 가로, 세로 길이가 모두 10인 것을 알 수 있다.

즉, 빨강색 ~ 파랑색의 은 가로가 10이고 세로가 4인 형태이고, 빨강색 ~ 초록색은 세로가 10이고 가로가 4인 형태이다.

그리고 첫 도형은 빨강색 칸 내에서 주어진다. 그리고 그 도형을 파랑색 칸과 초록색 칸으로 움직여주어야 한다.

그럼 빨강색 칸까지 합쳤을 때의 각 칸의 좌표 번호를 적어보면 이렇게 적어볼 수 있다.

.

문제에서는 파랑색칸과 초록색칸의 좌표번호가 0 ~ 6으로 표현되어 있지만 본인은 저렇게 생각해서 구현하였다.

왜냐하면, 어차피 빨강색 좌표에 떨어지는 블록들이 파랑색이든 초록색이든 칸을 움직이게 되면서 좌표번호가 계속해서 증가할 것이기 때문에, 이 증가한 좌표를 다시 0 ~ 6 으로 바꾸지 않고, 그 좌표 그대로 사용해 주었다.

그래서 ! 본인이 만든 맵의 형태는 " int Area[10][4][2] " 로 만들어 주었다.

각 차원에 가로인지 세로인지 이런 개념은 넣어주지 않았다. 단순히 10, 4, 2가 의미하는 값은 다음과 같다.

10 = 10칸이 존재한다. 파랑색이든 초록색이든 10칸이 존재하고 0 ~ 9 번 Index로 이루어져 있다.

4 = 파랑색은 세로로 4칸, 초록색은 가로로 4칸 까지만 존재한다.

2 = 파랑색과 초록색 2가지 색깔이 존재한다. 0 = 파랑색 , 1 = 초록색으로 계산해 주었다.

지금부터는 이 Index값들을(0 ~ 9) 그냥 Index를 증가시킨다, 감소시킨다 라고 표현하겠다. 뭐 파랑색 영역은 열을 증가시키고, 초록색 영역은 행을 증가시키면서 ~.. 이런 식의 표현을 쓰지 않고, 단순하게 Index값들을 증가시키거나 감소시킨다 라는 표현으로 이야기 하겠다. 그리고 4개의 줄을 0번줄, 1번줄, 2번줄, 3번줄 이라고 표현하겠다. 간단하게 이야기해서, 행과 열의 개념을 별로 신경쓰지 않고, 파랑색영역이든 초록색 영역이든 "Index번호와 x번째 줄" 이라고 통합해서 이야기 하겠다는 것이다.

.

위의 그림에서 1번 ~ 4번 좌표를 본인이 설명한 방식으로 이야기해보면 다음과 같이 이야기 하겠다는 것이다.

1번점 = 파랑색영역의 6번 Index의 2번 줄에 있습니다.

2번점 = 초록색영역의 8번 Index의 3번 줄에 있습니다.

3번점 = 파랑색영역의 9번 Index의 1번 줄에 있습니다.

4번점 = 초록색영역의 6번 Index의 0번 줄에 있습니다.

이런식으로 이야기하고, 관리하겠다는 것을 의미한다.

그럼 Area[10][4][2] 로 생성한 맵이 저장하는 값은 ?? 각 도형들이 가질 수 있는 고유한 도형 번호들을 하나 만들어서 넣어주었다.

여기서 말하는 '도형의 번호' 라는 것은 문제에서 제시한 1번 블록, 2번 블록, 3번 블록을 의미하는 것이 아닌, 각 블록이 갖는 고유의 번호를 만들어서 저장해 주었다.

간단하게 예를 들어보면, (x, y)에 1번 블록 생성, (x, y)에 2번 블록 생성, (x , y)에 3번 블록 생성, (x,  y)에 2번 블록 생성 이라는 입력이 떨어졌다고 가정해보자. 여기서 (x, y)는 빨강색에 존재하는 좌표이다.

그럼 우리는 위의 4개의 블록을 순서대로 파랑색과 초록색 영역에 옮겨주어야 한다.

이 대, 첫 번째 블록 = 1번, 두 번쨰 블록 = 2번, 세 번째 블록 = 3번, 네 번째 블록 = 4번 이런식으로 고유의 값을 만들어서 넣어주었다. 이렇게 구현한 이유는 밑에서 점점 더 구체적으로 알아보자.

2. 구현

본인은 이 문제의 구현과정을 크게 3가지로 나눠서 구현하였다.

1. 블록 세팅하기

2. 꽉 찬 라인(지워질 수 있는 라인) 체크하기

3. 특별한 칸 체크하기

이렇게 3가지로 나눠서 구현하였다. 각 단계별로 어떻게 구현했는지 구체적으로 알아보자.

2-1. 블록 세팅하기

빨강색 좌표에 블록을 놓을 위치와 블록의 종류가 주어지면, 이 블록을 파랑색 영역과 초록색 영역으로 옮겨주는 과정이다.

이 때, 파랑색 영역과 초록색 영역 따로따로 주의해줘야 할 블록들이 있다.

먼저 1번 타입의 블록은 블록 1개로만 이루어져 있기 때문에 상관이 없다. 해당 좌표에서 인덱스를 증가시켜 주면서, 다른 블록을 만나거나 맵의 끝에 도달하게 되면 멈추고 해당 좌표에 넣어주면 된다.

2번 타입의 블록을 보자. 2번 타입의 블록은 1x2 짜리 블록으로 가로로 긴 형태 'ㅡ'와 같은 형태의 블록이다.

이 블록을 파랑색 칸으로 옮기는 경우를 생각해보자. 파랑색 영역으로 옮길 때는 1번 타입의 블록과 같이, 인덱스를 증가시켜 주면서 다른 블록을 만나거나 맵의 끝에 도달하게 되면 멈춰주면 된다. 단 ! 주의 해야 할 것은, 처음 블록의 좌표가 (x, y)로 주어지게 되고, (x, y)에 놓아진 2번 타입의 블록은 실제로는 (x, y)와 (x, y + 1)을 차지하고 있는 블록의 형태이기 때문에 인덱스를 증가시킬 때, y + 1부터가 아닌, y + 2부터 증가시켜 주어야 한다.

그럼 이 2번타입의 블록을 초록색 영역으로 옮기는 과정을 생각해보자. 파랑색과 뭐가 다를까 ??

.

위의 그림과 같이 빨강색 영역의 (1, 1)에 놓아진 2번 타입의 도형을 파랑색 영역과 초록색 영역을 옮길 때를 구분해보자.

지금부터는 초록색과 파랑색이 갖는 '4줄'에 대해서 신경을 써야 한다.

먼저, 위에서 말했던 파랑색 영역으로 옮길 때는 다음과 같이

.

이렇게 4개의 줄 중에서 한 줄에 대해서만 고려를 해주면 된다.

그런데 초록색으로 옮길때는 ??

.

이 그림과 같이 4개의 줄 중에서 2개의 줄에 대해서 고려를 해주어야 한다. 왜 2개의 줄을 고려해주어야 할까 ??

이런 경우가 존재하기 때문이다.

.

위의 그림과 같이 기존에 초록색의 9번 Index에 1번 타입의 블록이 하나 있다면, (1, 1)에서 2번타입의 도형을 초록색 영역으로 옮겼을 때, 위치는 위와 같이 존재한다. 분명 9번 Index의 1번 줄은 비어있음에도 불구하고, 9번 Index의 2번 줄이 다른 도형으로 채워져 있기 때문에 더 이상 움직일 수가 없다. 따라서 ! 2번 타입의 도형을 초록색 영역으로 옮길 때는, 2개의 줄을 고려해주어야 한다.

그럼 이제 3번 타입의 블록을 생각해보자. 3번 타입의 블록은 2x1로써, '|'와 같은 형태를 가진 블록이다.

이 블록은 딱 봐도 초록색 영역으로 옮길 때는 한 줄만 고려하면 되지만, 파랑색 영역으로 옮길때는 2개의 줄을 고려해 주어야 한다.

위에서 2번 타입의 블록을 초록색 영역으로 옮길 때와 마찬가지로, 3번 타입의 블록을 파랑색 영역으로 옮길 때는 2개의 줄을 고려해 주어야 한다.

밑에서도 이 개념이 중요하게 적용되는 과정이 하나 더 있으니, 정리한번 하고 코드로 넘어가보자.

1. 1 x 1 타입의 블록은 , 초록색영역이든 파란색영역이든 그 자체로 한 칸만 차지하고 있으므로 해당 Index , 줄 번호만 고려.

2. 1 x 2 타입의 블록은 , 초록색영역으로 갈 때, 2개의 줄을 차지하면서 내려가므로, 2개의 줄을 고려해줘야 한다.

3. 2 x 1 타입의 블록은 , 파란색영역으로 갈 때, 2개의 줄을 차지하면서 내려가므로, 2개의 줄을 고려해줘야 한다.

그럼 이 부분을 코드로 한번 보자.

void Setting_Block(int Shape, int x, int y)
{
    // 1 = . / 2 = ㅡ / 3 = |
    if (Shape == 1)
    {
        int B_Idx = y + 1;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        
        int G_Idx = x + 1;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 2;
    }
    else if (Shape == 2)
    {
        int B_Idx = y + 2;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        Area[B_Idx - 2][x][0] = Figure_Num;
 
        int G_Idx = x + 1;
        while (G_Idx < 10 && (Area[G_Idx][y][1] == 0 && Area[G_Idx][y + 1][1] == 0)) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num;
        Area[G_Idx - 1][y + 1][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 4;
    }
    else
    {
        int B_Idx = y + 1;
        while (B_Idx < 10 && (Area[B_Idx][x][0] == 0 && Area[B_Idx][x + 1][0] == 0)) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        Area[B_Idx - 1][x + 1][0] = Figure_Num;
 
        int G_Idx = x + 2;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num;
        Area[G_Idx - 2][y][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 4;
    }
}

이 코드가 본인이 구현한 블록을 세팅하는 코드이다.

먼저 하나의 블록을 입력받게 되면, 파랑색 영역 초록색 영역 2개의 영역으로 움직여 주어야 한다.

1번 타입의 블록일 때는 빈 칸이 안나올 때 까지 Index를 증가시키다가 적절한 칸에 넣어주면 된다. 신경써야 할 줄도 한 줄만 신경쓰면 된다.

2번 타입의 블록일 때는 파랑색은 한 줄만 신경써도 되지만, 초록색은 2개의 줄을 신경 써주어야 한다고 했다.

그래서 line24)를 보게 되면, 빈 칸을 찾을 때 까지 Index번호가 증가하는 조건문이 저렇게 들어간 것이다.

line24)에서 보게되면, y번 줄도 빈 칸이고, y + 1번 줄도 빈 칸일 때만 Index번호가 증가한다는 것을 확인할 수 있다.

3번 타입의 블록일 때는 반대로, 파랑색 영역으로 옮길 때 2개의 줄을 신경 써주어야 한다고 했다.

line33)에서 보게 되면, x번 줄도 빈 칸이고, x + 1번 줄도 빈 칸일 때만 Index번호가 증가한다는 것을 확인할 수 있다.

그리고 위의 코드에서 보이는 'Figrue_Num' 이라는 변수가 본인이 만들어준 도형들이 갖는 고유의 번호이다.

그리고 Block_Cnt라는 변수를 계산하는 것이 보이는데, 이 변수는 밑에서 설명하도록 하겠다.

2-2. 꽉 찬 라인(지워질 수 있는 라인) 체크하기

1번 과정을 통해서 도형을 입력받고 파랑색 영역, 초록색 영역으로 옮기게 되면 이 도형들로 인해서 '꽉 찬 라인' 이 발생할 수 있다. 문제에서 보면, 이렇게 꽉 찬 라인은 지우면서 점수를 1점 획득하고, 다시 이후에 있는 도형들을 움직여 주어야 한다고 되어있다.

그럼 이게 '꽉 찬 라인'을 처리해보자.

먼저, 꽉 찬 라인을 찾는 과정은 어렵지 않다. 단순하게 for문을 통해서 찾아주면 되기 때문이다.

6번 Index부터 9번 Index까지(4번 5번 Index는 어차피 특별한 점이라고 해서 3번에서 따로 처리합니다.) 4개의 줄을 탐색하면서

꽉 차있는지 아닌지를 판단해주면 된다. 그래서 하나의 줄이 꽉 차 있다는 결과를 얻었다고 생각해보자.

그럼 우리가 해줘야 할 과정이 ?? 해당 줄을 비워주고, 다른 블록들을 움직여 주면 된다. 그런데 ! 여기서 끝이 나버리면 안된다. 왜냐하면, 해당 줄을 비워주고, 다른 블록들을 다시 움직여 줌으로써 다시 꽉 찬 라인이 발생할 수 있기 때문이다.

그럼 이 경우에는 ? 이 과정을 또 해주어야 한다. 그래서 본인은 이 과정을 재귀로 구현해 주었다. 코드로 보면 다음과 같다.

void Remove_Full_Block()
{
    bool Flag = false;
    for (int Color = 0; Color < 2; Color++)
    {
        for (int i = 6; i < 10; i++)
        {
            int Cnt = 0;
            for (int j = 0; j < 4; j++)
            {
                if(Area[i][j][Color] != 0) Cnt++;
            }
            if (Cnt == 4)
            {
                Flag = true;
                Score++;
                Remove(i, Color);
                Move(i, Color);
            }
        }
    }
    if(Flag == true) Remove_Full_Block();
}

line4)는 2가지 영역을 의미한다. 0 = 파랑색 영역, 1 = 초록색 영역

line6)에서 보면 6번 Index부터 9번 Index까지 반복하면서 꽉 찬 줄을 찾는 과정이다.

line9 ~ 12)는 각 Index에서 4개의 줄을 탐색하면서, 채워져 있는 블록의 갯수를 Count하는 과정이다. 만약, 이 Count의 값이 4라면, 해당 Index는 꽉 찬 줄이 되는 것이다. 이에 대한 처리가 line13) 에 걸려있는 조건문이다.

꽉 찬 줄이 발생하면서 line 15 ~ 18)과 같이 점수를 획득해주고, 해당 줄을 지워주고, 블록을 움직여주는 과정이다.

Remove 함수와 Move함수에 대해서는 밑에서 따로 설명을 하겠다.

그런데 위에서 보면 Flag 라는 변수가 하나 존재한다. 이 Flag라는 변수는 초기에 false의 값을 가지고 있지만, 꽉 찬 라인이 발생하게 되면 true로 바뀐다는 것을 확인할 수 있다.

그리고 마지막 줄 line22)에서 보게되면, Flag가 true일 때만 재귀 호출을 하게 된다.

이 Flag변수가 true라는 것의 의미는 다음과 같다. "꽉 찬 라인이 발생해서, 그 라인을 지우고 다른 블록들을 옮기는 과정을 진행했습니다" 를 의미한다. 즉 ! 이런 경우에는 이 블록을 옮기는 과정에 의해서 또 한번의 꽉 찬 라인이 발생할 수 있다 라는 것을 의미한다. 따라서, 재귀 호출을 통해서 이에 대한 처리를 구현해 주었다.

2-3. 특별한 칸 체크하기
.

맵에서 4번 Index와 5번 Index는 파랑색 영역, 초록색 영역 모두에서 '특별한 영역'을 의미한다. 이 영역들에 도형이 있게 되면 그 수만큼 뒤에서부터 혹은 아래서부터 라인을 지워줘야 한다. 처음에 문제를 볼 때 이 부분이 무슨 말인지 되게 이해가 되지 않았었다. 혹시나, 본인과 같이 이해가 잘 되지 않았을 사람을 위해 설명하면, 도형을 놓았을 때, 4번 Index혹은 5번 Index에 도형이 만들어 진다고 생각해보자. 예를 들어서 다음과 같은 경우를 보자.
.

초록색영역은 빼고 ,파랑색 영역만 가져온 그림이다. 위와 같이 블록이 놓여져 있을 때, (1 , 2)에 1번 타입의 블록이 놓여졌다고 생각해보자. 저 블록을 파랑색 칸으로 옮기게 되면 ??

.

이렇게 될 것이다. 즉 ! 5번 Index에 블록이 생성된 것을 볼 수가 있다. 그럼 이 경우에는 4번 Index에는 블록이 없고, 5번 Index에는 블록이 존재하기 때문에, "특별한 영역을 의미하는 4, 5번 Index, 총 2개의 Index 중에서 한 개의 Index에 블록이 존재" 하게 되는 것이다. 즉 ! 1개의 Index에 블록이 존재하므로, 뒤에서 부터 한 줄을 지워주면 되는 것이다.

.

그럼 위의 경우는 ?? 옮겨보면 다음과 같이 될 것이다.

.

위와 같이, 4번 Index와 5번 Index, 총 2개의 Index에 도형이 존재하게 된다. 이렇게 되면 뒤에서부터 2줄을 지워줘야 하는 것이다.

초록색 영역도 마찬가지이다. 원리는 같기 때문에 따로 설명하지는 않겠다.

이 부분을 코드로 나타내면 다음과 같다.

void Check_Special_Point()
{
    for (int Color = 0; Color < 2; Color++)
    {
        int Cnt = 0;
        for (int SP = 4; SP < 6; SP++)
        {
            for (int i = 0; i < 4; i++)
            {
                if (Area[SP][i][Color] != 0)
                {
                    Cnt++;
                    break;
                }
            }
        }
        if (Cnt != 0)
        {
            for (int i = 0; i < Cnt; i++)
            {
                Remove(9, Color);
                Move(9, Color);
            }
        }
    }
}

line6)에서 보게 되면, 4번 Index부터 5번 Index, 2개의 Index에 대해서만 진행된다. 왜냐하면 특별한 칸에 블록이 놓여져 있는지 확인하기 위함이다. line8)에서 보면, 4개의 줄을 확인하는데, 도형이 있다면 도형이 있는 그 줄 수만큼 Cnt라는 변수의 값이 증가하게 된다. line 17 ~ 22)에서 보게 되면, 특별한 영역의 Index에 블록이 있는 Index의 수 만큼 줄을 지워주고 도형을 옮겨주는 과정을 진행하고 있다.

3. Remove & Move 함수 구현

(이 부분의 내용은 특별한 알고리즘이나 특별한 방법이 사용되는 부분은 아닙니다. 본인이 이해하시기 쉬운 방법으로 구현하시는 것이 가장 좋은 방법이라고 생각합니다. 이 글에서는 제가 사용했던 방법을 소개하겠습니다.)

그럼.. 지금부터는 Remove와 Move함수에 대해서 알아보자.

먼저 Remove함수는 간단하다. 매개변수로, (지우고자 하는 Index번호 , 색깔) 이 주어진다.

void Remove(int Idx, int Color)
{
    for (int i = 0; i < 4; i++)
    {
        if (Area[Idx][i][Color] != 0)
        {
            Block_Cnt--;
            Area[Idx][i][Color] = 0;
        }
    }
}

위와 같이, 지우고자하는 Index번호와 색깔이 주어지게 되면, 해당 색깔의 Index번호의 4개의 줄에 대해서 도형을 지워주면 된다. 이게 도형을 지울 때, 한 줄이 꽉 차서 지우는 경우가 존재하고, 또 하나는 특별한 영역 때문에 꽉 차지도 않았음에도 지워야 하는 경우가 존재해서, 위와 같이 구현해 주었다. Block_Cnt변수는 마지막에 설명하겠다.

문제는 Move함수이다. 도형을 옮기는 부분인데, 본인이 구현할 때 가장 어려웠던 부분은 "블록의 짝궁을 찾는 과정"이였다. 일단, 먼저 블록을 무조건 하나하나씩 옮기는 것은 문제의 조건에 위배되기 때문에 그렇게 옮길 수는 없다.

왜냐하면 위에서도 이야기했던 상황을 한번 가져와보면...

.

이런 상황이 있었다. 처음 블록을 세팅할 때, 위와 같이 블록을 하나의 블록이라고 생각해야지, 1x2 크기의 블록 혹은 2x1 크기의 블록을 1x1짜리 2개로 생각해서 각각을 움직여 줄 수는 없다. 도형을 세팅하는 것 뿐만 아니라,  도형을 옮겨줄 때도 마찬가지이다.

절대로 블록 하나하나를 옮겨줄 수는 없다. 그런데 ! 문제는 도형이 마음대로 짤려 나가버리는 경우가 발생한다는 것이다.

예를 들어보면 이런 상황이다.

.

위의 그림에서 도형에 숫자를 2개씩 적어놨는데 의미는 '블록의 고유의번호(블록의 타입)' 이다.

첫 번째로 1번 타입의 블록이 9번 Index의 0번줄에 위치했고, 두 번째로 1번 타입의 블록이 9번 Index의 2번째 줄에 위치했다...

이런식으로 5개의 블록이 있는 상태에서 6번 블록이 위와 같이 위치했다고 생각해보자. 저기는 특별한 영역이다. 따라서 마지막 한줄을 지워야 한다. 그럼 지금부터 마지막 줄을 지우고, 3번 블록 '3(2)' 라고 표현되어 있는 블록에 집중해보자.

마지막 줄이 지워지게 되면 ?

.

이렇게 되어버린다. 3번 블록이 원래는 1 x 2 짜리 형태인 2번 타입의 블록이었는데, 마치 1번 타입의 블록처럼 바뀌었다.

즉 ! 이 블록은 지금부터는 1번 블록과 똑같다. 1번 블록처럼 움직여 주면 된다.

1번 블록처럼 움직여 주면 된다는 것은 ?? "하나의 줄에 대해서만 생각을 해주면 된다." 라는 것이다.

너무나도 당연한 이야기지만, 우리 위에서 이야기 했던 1단계인 '블록 세팅하기' 과정을 생각해보자. 분명히 다른 블록들에 대해서는 영역에 따라서 2개의 줄을 생각해 줘야 하는 블록들이 있었다.

그래서 본인은 움직이는 과정을 진행하기에 앞서, 해당 블록의 짝꿍을 찾아주었다. 짝꿍이라는 것은 초기에 만들어 졌을 때, 함께 움직였던 블록을 찾는 것이다. 물론, 1번 타입의 블록 같은 경우에는 짝꿍이 없다. 1 x 1 짜리 블록이기 때문이다.

그런데, 2번 타입 혹은 3번 타입 블록은 짝꿍이 있기 때문에 이 짝꿍들을 찾아주어야 한다. 그리고 짝꿍을 찾았으면, 색깔 영역에 따라서 2개의 줄을 고려할지 하나의 줄만 고려할지를 생각해 주면 된다.

그럼 짝꿍은 어떻게 찾을까 ?? 짝꿍은 무조건적으로 현재 블록을 기준으로 '상, 하, 좌, 우' 4방향 중에 하나에는 존재한다.

그 블록이 2번 타입의 블록이든 3번 타입의 블록이든 무조건 상하좌우 4방향 중 한 방향에는 짝꿍이 존재한다.

물론 1번 타입의 블록은 없을 것이다. 또한, 2번 타입의 블록이든, 3번 타입의 블록이든, 위에서 본 예시와 같이 짝궁이 짤려나가서 없는 경우도 존재한다. 그럼 먼저, 현재 Index와 줄을 기준으로 상하좌우를 탐색해서 짝꿍을 찾아보자. 근데, 짝꿍을 어떻게 찾아??

이 과정을 위해서 본인은 블록들의 "고유의 번호"를 만들어서 저장해 준 것이다. 그냥 블록 타입으로 저장해주면 안되나 ??

그럼 짝꿍을 정확하게 못 찾을 수도 있다. 당장 위의 그림만 봐보도록 하자. 실제로 3번 블록의 짝꿍은 마지막줄이 없어짐에 따라서 없어져버렸다. 그런데 블록 타입으로 구분을 한다면 ? 3번의 블록타입은 '2'이고, 3번 왼쪽에도, 3번 아래쪽에도 블록 타입이 '2' 이기 때문에 정확한 짝꿍이 아님에도 불구하고 짝꿍이라고 오해하는 경우가 생겨버린다. 따라서 ! 본인은 블록의 '고유의 번호'를 만들어서 저장해 주었다. 그리고 상하좌우를 탐색하면서 짝꿍을 찾을 때에도 이 '고유의 번호'를 찾는 것이다.

그럼 짝꿍을 찾은 경우와 못 찾은 경우로 구분을 해보자.

1. 짝꿍을 못 찾은 경우 ??

- 1번 블록과 똑같다. 움직여 줄 때, 자신이 위치한 줄에서 Index번호만 증가시키면서 빈 칸을 찾아다니면 된다.

- 1번 블록은 짝꿍이 없으므로 당연히 못 찾을 것이고, 2번 블록이나 3번 블록은 짝꿍이 짤려나가서 못 찾는 경우가 존재한다.

  이 경우에는 그냥 1번 블록처럼 생각해서 옮겨주면 된다. 기존의 2번블록, 3번블록을 움직일 때 처럼 2개의 줄을 고려하면서

  움직여 줄 필요가 없다.

2. 짝꿍을 찾은 경우 ??

- 본인은 이 경우에 "내가 움직일 수 있는 거리 vs 짝꿍이 움직일 수 있는 거리" 를 비교해서, 더 짧은 쪽으로 움직여 주었다.

   .

  이런 경우를 보자. 현재 8번 Index의 2번 줄에 내가 있고, 그 좌표로부터 짝궁을 찾았더니 8번 Index에 3번 줄에 있다고 생각해보

  자. 이 때, 내가 움직일 수 있는 거리는 1칸 이지만, 짝꿍이 움직일 수 있는 거리는 0칸이다. 그럼 결과적으로 이 블록이 움직일 수

  있는 거리는 ?? 0칸이 된다. 즉 ! "내가 움직일 수 있는 거리 vs 짝꿍이 움직일 수 있는 거리" 를 비교했을 때, 더 적게 움직일 수

  있는 거리가 해당 블록이 움직일 수 있는 거리가 된다는 것이다.

.

그럼 이경우는 ?? 내가 8번 Index에 1번줄에 있는데, 상하좌우를 탐색해서 짝꿍을 찾았더니, 7번 Index의 1번줄에 있다 라는 것을 찾았다. 그래서 "내가 움직일 수 있는 거리 vs 짝꿍이 움직일 수 있는 거리" 를 적용시키기 위해서 각각의 거리를 구했더니...

내가 움직일 수 있는 거리 = 1칸 이 나왔지만, 짝꿍은 '나'에 가려져서 움직일 수 있는 거리 = 0칸이라고 나왔다.

그래서 결과적으로 이 블록이 움직일 수 있는 거리 = 0칸 이 된다. 라고 말을 하면 뭔가 이상하다. 딱 봐도 위의 도형은 오른쪽으로 한 칸 더 움직일 수가 있다. 즉 ! 이렇게 "짝꿍이 나에 가려져서 움직일 수 없는 경우"가 존재한다. 이런 경우에는 간단하게, "짝꿍이 움직일 수 있는 거리 = 무한대" 로 설정해 주었다. 그럼 무조건 "내가 움직일 수 있는 거리"가 더 짧아지게 될 것이고, 정확하게 움직일 수 있는 칸수를 구할 수가 있다. 코드로 알아보자.

void Move(int Idx, int Color)
{
    if (Idx == 3) return;
    
    int Delete_Idx = Idx - 1;
    for (int i = 0; i < 4; i++)
    {
        if (Area[Delete_Idx][i][Color] == 0) continue;
 
        int x = Delete_Idx;
        int y = i;
        int Value = Area[x][y][Color];
        bool Flag = false;
 
        for (int j = 0; j < 4; j++)
        {
            int xx = Delete_Idx + dy[j];
            int yy = y + dx[j];
 
            if (xx >= 4 && xx < 10 && yy >= 0 && yy < 4)
            {
                if (Area[x][y][Color] == Area[xx][yy][Color])
                {
                    Flag = true;
                    int Temp_x = x + 1;
                    int Cnt = 1;
                    while (1)
                    {
                        if (Temp_x < 10 && Area[Temp_x][y][Color] == Value)
                        {
                            Cnt = 2e9;
                            break;
                        }
                        if (Area[Temp_x][y][Color] != 0 || Temp_x >= 10) break;
                        Temp_x++;
                        Cnt++;
                    }
                    Cnt--;
 
                    int Temp_xx = xx + 1;
                    int Cnt2 = 1;
                    while (1)
                    {
                        if (Temp_xx < 10 && Area[Temp_xx][yy][Color] == Value)
                        {
                            Cnt2 = 2e9;
                            break;
                        }
                        if (Area[Temp_xx][yy][Color] != 0 || Temp_xx >= 10) break;
                        Temp_xx++;
                        Cnt2++;
                    }
                    Cnt2--;
 
                    int Move_Cnt = Min(Cnt, Cnt2);
                    Area[x + Move_Cnt][y][Color] = Area[x][y][Color];
                    Area[xx + Move_Cnt][yy][Color] = Area[xx][yy][Color];
                    if (xx + Move_Cnt == x) Area[x][y][Color] = 0;
                    else Area[x][y][Color] = Area[xx][yy][Color] = 0;
 
                    break;
                }
            }
        }
        if (Flag == false)
        {
            int Temp_x = x + 1;
            int Cnt = 1;
            while (Temp_x < 10 && Area[Temp_x][y][Color] == 0)
            {
                Temp_x++;
                Cnt++;
            }
            Cnt--;
 
            Area[x + Cnt][y][Color] = Area[x][y][Color];
            Area[x][y][Color] = 0;
        }
    }
    Move(Idx - 1, Color);
}

위의 코드가 "하나의 Index를 옮기는 과정"을 나타낸 것이다. 모든 맵을 다 움직이는 과정이 아니다..

Move함수의 매개변수로는 (삭제한 Index, 색깔)이 주어진다. 블록을 움직이는 것 자체가 "한 줄이 삭제될 때에만 움직이는 연산이 진행" 되기 때문에(블록을 처음 세팅하는 과정은 따로 구현했으므로 빼고 이야기한 것이다.) 삭제한 Index를 매개변수로 호출해 주었다. 왜 ?? 삭제한 Index보다 더 큰 Index들은 절대로 움직이지 않기 때문이다. 

.

위의 그림을 봐보자. 위의 상태에서 빨강색 영역의 (2, 3)에 3번 타입의 블록을 놓고 파랑색 영역으로 옮기게 되면, 7번 Index가 꽉 차서 지워지게 된다. 그럼 7번 Index가 지워짐으로써 영향을 미치는 라인은 어디일까 ? 아마 6, 5, 4번 Index들일 것이다.

8번 Index, 9번 Index는 움직임이 있을까?? 없다. 즉 ! "x번 Index를 지우게 되면, x 이상의 Index들은 영향을 미치지 않는다".

그래서 매개변수로 "삭제한 Index"를 호출해준 것이다.

line5)에서 보게되면, Idx번 Index를 삭제했으므로, 내가 실제로 옮기려는 Index는 Idx - 1번으로 설정해 주고 있다.

line15)를 보게 되면, 상하좌우를 탐색하면서 짝꿍을 찾는 과정이다.

line22 ~ 63)을 보게되면, "짝꿍을 찾았을 때" 에 대한 구현 내용이다.

"내가 움직일 수 있는 거리"를 구하고, "짝꿍이 움직일 수 있는 거리"를 구한 후, 더 작은 값만큼 움직여 주는 것이다.

위에서도 말했듯이 주의해줘야 할 것은 "짝꿍이 나에 의해서 움직일 수 없는 상황"을 처리해 주는 것이다. 이 부분에 대한 처리는

line29, 44)에서 구현되어있다.

line65)는 짝꿍을 찾지 못했을 때이다. 짝꿍이 짤려나간건지, 애초에 1번 타입의 블록이었는지 그런 거 관심없다. 그냥 짝꿍이 없다라는 것은 1x1짜리 블록의 형태로 존재한다는 것이고, 이 블록을 옮겨주면 된다.

마지막 line80)에 보면 Idx - 1로 재귀 호출을 하고 있다. 왜 ?? 모든 Index들을 다 옮겨 주어야 하기 때문이다.

예를 들어서 7번 Index가 삭제되었다면, 4, 5, 6번 Index에 대해서 모든 블록들을 옮겨주어야 한다.

3번 2번 1번 0번 Index는 ?? 3번 Index부터는 빨강색 영역이기 때문에 도형이 존재하지 않는다. 그러므로 line3)에서 보면 이 재귀의 종료조건을 Idx == 3 으로 걸어주고 있다. 이렇게 Move함수를 구현해 주었다.

void Check_Special_Point()
{
    for (int Color = 0; Color < 2; Color++)
    {
        int Cnt = 0;
        for (int SP = 4; SP < 6; SP++)
        {
            for (int i = 0; i < 4; i++)
            {
                if (Area[SP][i][Color] != 0)
                {
                    Cnt++;
                    break;
                }
            }
        }
        if (Cnt != 0)
        {
            for (int i = 0; i < Cnt; i++)
            {
                Remove(9, Color);
                Move(9, Color);
            }
        }
    }
}

이 코드는 위에서 설명했던 "특별한 영역에 도형이 있을 시 처리하는 과정" 을 나타낸 코드이다.

이제 이 부분의 Move함수를 보자. (9, Color)로 Cnt만큼 호출되고 있다. 왜그럴까 ??

예를 들어서 특별한 영역에서 4번 Index에도 블록이 있고, 5번 Index에도 블록이 있다고 가정해보자. 그럼 ? 우리는 마지막 2줄을 지워야 한다. 이 과정을 ! "마지막 한줄을 지우고 옮기고, 마지막 한줄을 지우고 옮기고" 로 구현한 것이다. 그래서 9번 Index만 저렇게 Cnt만큼 호출한 것이다.

4. 정답 도출하기

정말 안타깝게도 이 문제에서 구해야 하는 것은 '획득한 점수'와 '현재 맵에 남아있는 블록의 갯수'이다. 그런데, 이에 대한 설명은 위에 하나도 없다. 사실 이부분은 문제의 중간중간에서 모두 구할 수 있다.

1. 남아있는 블록의 갯수

블록의 갯수가 추가되는 경우는 딱 한가지이다. 처음 블록이 생성되는 경우이다. 이 경우 외에는 블록이 추가될 수가 없다.

즉 ! 처음 블록이 생성될 때, 1번 과정을 진행할 때, 1번 타입의 블록은 블록의 갯수 + 2, 2번 타입 3번타입은 + 4를 해주면 된다.

왜 ? 1번 타입의 블록은 1x1짜리 이므로, 블록의 갯수가 1개인데 , 파랑색 영역과 초록색 영역으로 하나씩 가므로 총 2개 증가.

같은 원리로 2번 타입, 3번 타입의 블록은 1x2, 2x1짜리로 블록의 갯수가 2개인데, 각각 하나씩 가므로 총 4개 증가.

블록이 감소하는 경우는 2가지가 있다.

1. 꽉 찬 라인이라서 해당 라인을 지우는 경우.

2. 특별한 영역에 블록이 생성되서 가장 마지막 줄을 지우는 경우.

이 경우에는 Remove함수에서 블록을 지울 때마다 블록의 갯수를 -- 시켜주면 된다. 위의 Remove함수에 대한 설명을 다시한번 보게되면, 중간에 'Block_Cnt--' 라고 구현된 부분을 찾을 수 있을 것이다.

2. 점수 구하기

점수 구하는 것은 꽉 찬 라인이 존재할 때만 점수를 ++시켜 주면 된다. 사실 정답을 도출하는 과정이 굉장히 복잡한 문제였지, 정답을 도출하는 것은 간단한 문제인 것 같다.

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
using namespace std;
 
int N, Block_Cnt, Score, Figure_Num = 1;
int Area[10][4][2];
vector<pair<int, pair<int, int>>> V;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V.push_back(make_pair(a, make_pair(b, c)));
    }
}
 
void Setting_Block(int Shape, int x, int y)
{
    // 1 = . / 2 = ㅡ / 3 = |
    if (Shape == 1)
    {
        int B_Idx = y + 1;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        
        int G_Idx = x + 1;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 2;
    }
    else if (Shape == 2)
    {
        int B_Idx = y + 2;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        Area[B_Idx - 2][x][0] = Figure_Num;
 
        int G_Idx = x + 1;
        while (G_Idx < 10 && (Area[G_Idx][y][1] == 0 && Area[G_Idx][y + 1][1] == 0)) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num;
        Area[G_Idx - 1][y + 1][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 4;
    }
    else
    {
        int B_Idx = y + 1;
        while (B_Idx < 10 && (Area[B_Idx][x][0] == 0 && Area[B_Idx][x + 1][0] == 0)) B_Idx++;
        Area[B_Idx - 1][x][0] = Figure_Num;
        Area[B_Idx - 1][x + 1][0] = Figure_Num;
 
        int G_Idx = x + 2;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++;
        Area[G_Idx - 1][y][1] = Figure_Num;
        Area[G_Idx - 2][y][1] = Figure_Num++;
 
        Block_Cnt = Block_Cnt + 4;
    }
}
 
void Remove(int Idx, int Color)
{
    for (int i = 0; i < 4; i++)
    {
        if (Area[Idx][i][Color] != 0)
        {
            Block_Cnt--;
            Area[Idx][i][Color] = 0;
        }
    }
}
 
void Move(int Idx, int Color)
{
    if (Idx == 3) return;
    
    int Move_Idx = Idx - 1;
    for (int i = 0; i < 4; i++)
    {
        if (Area[Move_Idx][i][Color] == 0) continue;
 
        int x = Move_Idx;
        int y = i;
        int Value = Area[x][y][Color];
        bool Flag = false;
 
        for (int j = 0; j < 4; j++)
        {
            int xx = Move_Idx + dy[j];
            int yy = y + dx[j];
 
            if (xx >= 4 && xx < 10 && yy >= 0 && yy < 4)
            {
                if (Area[x][y][Color] == Area[xx][yy][Color])
                {
                    Flag = true;
                    int Temp_x = x + 1;
                    int Cnt = 1;
                    while (1)
                    {
                        if (Temp_x < 10 && Area[Temp_x][y][Color] == Value)
                        {
                            Cnt = 2e9;
                            break;
                        }
                        if (Area[Temp_x][y][Color] != 0 || Temp_x >= 10) break;
                        Temp_x++;
                        Cnt++;
                    }
                    Cnt--;
 
                    int Temp_xx = xx + 1;
                    int Cnt2 = 1;
                    while (1)
                    {
                        if (Temp_xx < 10 && Area[Temp_xx][yy][Color] == Value)
                        {
                            Cnt2 = 2e9;
                            break;
                        }
                        if (Area[Temp_xx][yy][Color] != 0 || Temp_xx >= 10) break;
                        Temp_xx++;
                        Cnt2++;
                    }
                    Cnt2--;
 
                    int Move_Cnt = Min(Cnt, Cnt2);
                    Area[x + Move_Cnt][y][Color] = Area[x][y][Color];
                    Area[xx + Move_Cnt][yy][Color] = Area[xx][yy][Color];
                    if (xx + Move_Cnt == x) Area[x][y][Color] = 0;
                    else Area[x][y][Color] = Area[xx][yy][Color] = 0;
 
                    break;
                }
            }
        }
        if (Flag == false)
        {
            int Temp_x = x + 1;
            int Cnt = 1;
            while (Temp_x < 10 && Area[Temp_x][y][Color] == 0)
            {
                Temp_x++;
                Cnt++;
            }
            Cnt--;
 
            Area[x + Cnt][y][Color] = Area[x][y][Color];
            Area[x][y][Color] = 0;
        }
    }
    Move(Idx - 1, Color);
}
 
void Remove_Full_Block()
{
    bool Flag = false;
    for (int Color = 0; Color < 2; Color++)
    {
        for (int i = 6; i < 10; i++)
        {
            int Cnt = 0;
            for (int j = 0; j < 4; j++)
            {
                if(Area[i][j][Color] != 0) Cnt++;
            }
            if (Cnt == 4)
            {
                Flag = true;
                Score++;
                Remove(i, Color);
                Move(i, Color);
            }
        }
    }
    if(Flag == true) Remove_Full_Block();
}
 
void Check_Special_Point()
{
    for (int Color = 0; Color < 2; Color++)
    {
        int Cnt = 0;
        for (int SP = 4; SP < 6; SP++)
        {
            for (int i = 0; i < 4; i++)
            {
                if (Area[SP][i][Color] != 0)
                {
                    Cnt++;
                    break;
                }
            }
        }
        if (Cnt != 0)
        {
            for (int i = 0; i < Cnt; i++)
            {
                Remove(9, Color);
                Move(9, Color);
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        int t = V[i].first;
        int x = V[i].second.first;
        int y = V[i].second.second;
        Setting_Block(t, x, y);
        Remove_Full_Block();
        Check_Special_Point();
    }
    cout << Score << endl << Block_Cnt << 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;
}