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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

백준의 모노미노도미노(19235) 문제와 굉장히 비슷한 문제이다.

19235번 모노미노도미노 문제와 차이가 있다면, 모노미노도미노 문제에서는 블럭이 사라지게 될 경우, 나머지 블럭들이 움직일 수 있는 칸 끝까지 움직여야 했지만, 이 문제 같은 경우에는 블럭이 사라지게 될 경우, 사라진 행 혹은 열의 갯수만큼만 블럭들이 움직이게 된다.

먼저, 문제의 변수설정, 접근법, 전체적인 로직은 본인이 작성해놓은 19235번 문제풀이와 굉장히 비슷하니, 먼저 이 문제에 대한 풀이를 보기 전에 아래의 풀이를 먼저 보고 오는 것을 권장한다.

[ 백준 - 모노미노도미노(19235) 풀이 바로가기 ]

위의 글을 읽었다고 가정하고, 위의 풀이와 중복되는 이야기(문제의 전체적인 로직, 접근법, 변수설정)는 이 글에서는 하지 않도록 하겠다. 가장 큰 차이가 있는 '블럭을 움직이는 경우' 에 대해서만 이야기를 할 것이다.

( 본인이 이 문제를 해결할 때, 19235번 코드를 복사해서 풀지는 않았기에 19235번 풀이 코드와 약간의 차이는 있을 수 있지만 전체적인 로직은 똑같습니다 ! )

가장 크게 바뀐 부분은 아무래도 'Move' 함수 부분일 것이다. 왜냐하면, 위에서도 이야기 했듯이 모든 로직 및 풀이가 똑같지만, 블럭이 사라지게 될 경우, 나머지 블럭들을 움직이는데 가장 큰 차이가 있기 때문이다.

기존의 Move함수가 진행되는 과정에 대해서 정말 간략하게만 이야기를 하자면 다음과 같다.

1. 움직여야 하는 블럭을 찾는다.

2. 1)에서 찾은 블럭의 짝꿍을 찾는다.

3. 2)에서 찾은 짝궁과 개별적으로 블럭을 움직일 수 있을 때 까지 움직여준다.

   3-1. 2)에서 짝궁을 찾지 못했다면, '1번블럭'으로 판단해주고 해당 블럭만 움직여 주면 된다.

   3-2. 2)에서 짝궁을 찾았다면, 각각의 블럭들을 움직인 후, 짝궁과 나 를 비교했을 때 더 짧게 움직인 칸수 만큼

        움직여준다.

4. 이 과정을 모든 행 혹은 열에 대해서 재귀를 통해서 반복해준다.

마지막 4번 과정을 위해서 Move함수의 인자로는 [ 행 or 열의 번호 , 색깔 ] 이 2개의 인자를 이용해서 구현해 주었다.

이 문제에서는 위의 과정에서 3번 과정에 변화가 일어난다. 왜냐하면 이 문제에서는 움직이는 칸수가 사라진 행 혹은 열의 갯수만큼만 움직여지기 때문에, "움직일 수 있을 때 까지" 움직이는 과정이 움직일 칸 수 만큼만 움직이도록 구현되어야 한다.

그런데 본인은 조금은 다르게 구현해 보았다. 무조건 1칸씩만 움직이도록 구현해 주었다.

이게 무슨말인지 알아보자.

.

모노미노도미노 맵에서 초록색 부분만 짤라서 가져온 것이다.

위와 같은 상황에서 'A'블록이 떨어진다고 가정을 해보자. 그러면 가장 아래 2줄에 사라지게 될 것이고,  'B'블록과 'C'블록은 각각 2줄씩 아래로 움직여야 하는 상황이 된다.

본인은 이 부분을 2줄이 없어지고, 나머지 블록들이 2칸씩 더 아래로 내려오는 상황으로 계산하지 않고, 1줄 없어지고, 나머지 블록들이 1칸씩 내려오는 상황을 2번 반복하는 것으로 구현해 주었다.

즉, 위의 'A'블록이 떨어졌을 때 본인이 구현한 방식대로 진행된다면 다음과 같다.

위의 그림을 왼쪽부터 1번, 2번, 3번, 4번, 5번 이라고 표현하겠다.

1번은 가장 먼저 A가 떨어졌을 때의 상황이다.

2번은 A가 떨어짐으로써 2줄이 사라지지만, 가장 마지막 줄 부터 판단했을 때 지워지는 줄이 생겼으므로, 해당 줄을 지워주는

과정이다.

3번은 2번 과정에서 가장 마지막 줄이 사라짐으로써, 나머지 블록들이 한 칸 내려온 상황이다.

4번은 또 하나의 줄이 사라지는 과정이다.

5번은 나머지 블록들이 또 한 칸씩 내려오는 과정이다.

위의 과정처럼, 본인은 몇 줄이 사라지던간에, 해당 줄들을 모두 삭제한 후에, 한번에 움직이는 것이 아니라, 한 줄씩 삭제시키고 나머지를 한 칸씩 움직이는 것으로 구현을 해 주었다.

이를 코드로 구현하면 다음과 같다.

void Move(int Index, int Color)
{
    if (Index == 3) return;
    
    int Idx = Index - 1;
    for (int i = 0; i < 4; i++)
    {
        if (Area[Idx][i][Color] == 0) continue;
        
        int Pos = i;
        int F_Num = Figure_Num[Area][Idx][i];
        pair<int, int> Shape = Find_Partner(Idx , Pos, Color);
        
        if (Shape.first == 1)
        {
            int n_Idx = Idx + 1;
            Area[n_Idx][i][Color] = Area[Idx][i][Color];
            Area[Idx][i][Color] = 0;
        }
        else if (Shape.first == 2)
        {
            int P_Idx = Idx + dx[Shape.second];
            int P_Pos = Pos + dy[Shape.second];
            if (Color == 0)
            {
                int Standard_Idx = Max(P_Idx, Idx);
                int Partner_Idx = Min(P_Idx, Idx);
                int n_Idx = Standard_Idx + 1;
                int nP_Idx = Partner_Idx + 1;
                Area[n_Idx][i][Color] = Area[Standard_Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[Partner_Idx][i][Color];
                Area[Partner_Idx][i][Color] = 0;
            }
            else
            {
                int n_Idx = Idx + 1;
                int nP_Idx = P_Idx + 1;
                Area[n_Idx][i][Color] = Area[Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[P_Idx][i][Color];
                Area[Idx][i][Color] = 0;
                Area[P_Idx][i][Color] = 0;
            }
        }
        else
        {
            int P_Idx = Idx + dx[Shape.second];
            int P_Pos = Pos + dy[Shape.second];
            if(Color == 0)
            { 
                int n_Idx = Idx + 1;
                int nP_Idx = P_Idx + 1;
                Area[n_Idx][i][Color] = Area[Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[P_Idx][i][Color];
                Area[Idx][i][Color] = 0;
                Area[P_Idx][i][Color] = 0;
            }
            else
            {
                int Standard_Idx = Max(Idx, P_Idx);
                int Partner_Idx = Min(Idx, P_Idx);
                int n_Idx = Standard_Idx + 1;
                int nP_Idx = Partner_Idx + 1;
                Area[n_Idx][i][Color] = Area[Standard_Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[Partner_Idx][i][Color];
                Area[Partner_Idx][i][Color] = 0;
            }
        }
    }
    Move(Index - 1, Color);
}
 

기존의 코드인 모노미노도미노(19235)와 굉장히 코드가 다르다. 하지만 전체적인 로직은 똑같다.

구현할 때 조금 더 깔끔하게 구현해보겠다고 한건데, 사실 더 깔끔해 졌는지는 모르겠다..

line12)에서 보면 가장 먼저 나의 짝꿍을 찾는 과정을 진행하게 된다.

짝꿍은 반드시 '나'를 기준으로 상하좌우 4방향 중 한 곳에 존재하고 이를 통해서 짝꿍을 찾아주었다.

이 부분에 대한 구체적인 설명은 위에 링크를 걸어놓은 모노미노도미노(19235) 풀이에 적혀있으니 참고하길 바란다.

line12)에서 pair로 return받은 이유는 짝꿍을 찾았을 때, { 블럭의 번호 , 짝꿍이 있는 위치 } 이 2개의 값을 한번에 return 받아야 해서 pair로 return 받아 주었다.

만약 블럭의 모양이 2번 블럭이거나 3번 블럭이었다면 "기준이 되는 블럭" 과 "파트너 블럭" 2개의 블럭으로 나누어 주었다.

이를 나누는 기준은 "누가 더 마지막 줄에 가까운지" 를 통해서 나눠주었다.

초록색 영역에서는 3번블럭이, 파랑색 영역에서는 2번블럭이 이에 영향을 미치게 된다. 아래의 상황들을 보자.

.

'나'를 기준으로 짝꿍을 찾았더니, 짝꿍이 나보다 한칸 윗줄에 있는 상황을 가정해보자.

이 경우, "기준이 되는 블럭"은 '나'가 있는 블럭이 된다. 왜 ?? 짝꿍에 비해서 내가 더 마지막 줄에 더 가깝기 떄문이다.

반대의 상황도 똑같다.

.

'나'를 기준으로 짝궁을 찾았더니, 짝꿍이 나보다 한칸 더 아랫줄에 있게 된다.

이 경우, "기준이 되는 블럭"은 '짝'이 있는 블럭이 된다. 왜 ?? 짝궁이 나에 비해서 마지막 줄에 더 가깝기 때문이다.

그럼, 지금부터는 '나'와 '짝꿍'의 개념이 사라지고, 기준이 되는 블럭과 파트너 블럭으로 표현하겠다.

여기서 무조건 한 칸을 아래로 움직인다고 했으니, 기준이 되는 블럭과 파트너 블럭을 '을 모두 한 칸씩 아래로 움직인 후에 기존의 위치에 있는 값들을 없애주겠다. 여기서 기존의 위치라는 것은, 본인은 도형마다 고유의 번호를 저장해서 표현해 주었기 때문에, 해당 번호를 움직인 후의 위치로 설정해 주는 것이다. 이 또한, 19235번 풀이에 적혀있다.

그럼 위의 도형이 'A번' 도형이였다고 가정해보자.

.

도형을 옮기게 되면, 왼쪽 그림과 같이 'A번'이 설정될 것이고, 기존의 'A'번은 그대로 남아있을 것이다.

따라서 기존의 'A'번을 지워주기 위해서 '기준 블럭' 과 '파트너 블럭'이 있었던 위치에 있는 값을 0으로 바꿔주면 오른쪽 그림과 같이 변하게 된다. 그런데 뭔가 이상하다. 'A'라고 표현될 부분에 '0'이라고 표현된 부분이 있다.

왜 그렇게 될까 ??

바로 파트너 블럭이 있던 위치에서 아래로 한 칸 내려오게 되면 그 위치는 곧 기준 블럭이 있었던 위치가 된다.

그런데 ! 기준이 있었던 위치를 '0'으로 바꿔줘버리기 때문에 위와 같은 상황이 발생한다.

따라서, 초록색 영역에서 3번 도형일 경우에는 이 부분에 대해서 주의를 해주어야 한다.

그래서 line65)에서 보면, '0'으로 바꿔주는 부분은 파트너 블럭이 원래 있었던 곳만 바꿔준다.

파랑색 영역은 구체적으로 설명을 하진 않겠지만, 로직은 동일하다.

'나'를 기준으로 짝꿍을 찾은 후에, '짝꿍'과 '나'의 위치를 비교해서 더 마지막줄에 가까운 블럭을 '기준 블럭' 으로 삼게 되고, 그렇지 않은 블럭을 '파트너 블럭'으로 삼게 된다.

그 이후, 한 칸씩 움직이게 되는데 파랑색 영역에서는 2번 블럭이 위의 그림과 같은 상황이 발생하게 된다.

파트너블럭에서 한칸 더 움직이게 되면 그 칸이 기준블럭이 되는 경우이다.

이 부분을 위해서 line32)에서도 보면, 파트너 블럭이 있었던 위치의 값만 0으로 바꿔주는 과정을 진행해 주었다.

[ 소스코드 ]

#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; }
int Max(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)
{
    if (Shape == 1)
    {
        int B_Idx = y + 1;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++; B_Idx--;
        Area[B_Idx][x][0] = Figure_Num;
        
        int G_Idx = x + 1;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++; G_Idx--;
        Area[G_Idx][y][1] = Figure_Num++;
        
        Block_Cnt += 2;
    }
    else if (Shape == 2)
    {
        int B_Idx = y + 2;
        while (B_Idx < 10 && Area[B_Idx][x][0] == 0) B_Idx++; B_Idx--;
        Area[B_Idx][x][0] = Figure_Num;
        Area[B_Idx - 1][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++; G_Idx--;
        Area[G_Idx][y][1] = Figure_Num;
        Area[G_Idx][y + 1][1] = Figure_Num++;
 
        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++; B_Idx--;
        Area[B_Idx][x][0] = Figure_Num;
        Area[B_Idx][x + 1][0] = Figure_Num;
        
        int G_Idx = x + 2;
        while (G_Idx < 10 && Area[G_Idx][y][1] == 0) G_Idx++; G_Idx--;
        Area[G_Idx][y][1] = Figure_Num;
        Area[G_Idx - 1][y][1] = Figure_Num++;
 
        Block_Cnt += 4;
    }
}
 
void Remove(int Idx, int Color)
{
    for (int i = 0; i < 4; i++)
    {
        if (Area[Idx][i][Color] == 0) continue;
        
        Area[Idx][i][Color] = 0;
        Block_Cnt--;
    }
}
 
pair<int, int> Find_Partner(int Idx, int Pos, int Color)
{
    if (Color == 0)
    {
        for (int i = 0; i < 4; i++)
        {
            int n_Idx = Idx + dx[i];
            int n_Pos = Pos + dy[i];
 
            if (n_Idx >= 4 && n_Idx < 10 && n_Pos >= 0 && n_Pos < 4)
            {
                if (Area[Idx][Pos][Color] == Area[n_Idx][n_Pos][Color])
                {
                    if (Idx == n_Idx) return{ 3, i };
                    return{ 2, i };
                }
            }
        }
        return{ 1, -1 };
    }
    
    for (int i = 0; i < 4; i++)
    {
        for (int i = 0; i < 4; i++)
        {
            int n_Idx = Idx + dx[i];
            int n_Pos = Pos + dy[i];
 
            if (n_Idx >= 4 && n_Idx < 10 && n_Pos >= 0 && n_Pos < 4)
            {
                if (Area[Idx][Pos][Color] == Area[n_Idx][n_Pos][Color])
                {
                    if (Idx == n_Idx) return{ 2, i };
                    return{ 3, i };
                }
            }
        }
        return{ 1, -1 };
    }
}
 
void Move(int Index, int Color)
{
    if (Index == 3) return;
    
    int Idx = Index - 1;
    for (int i = 0; i < 4; i++)
    {
        if (Area[Idx][i][Color] == 0) continue;
        
        int Pos = i;
        int F_Num = Figure_Num[Area][Idx][i];
        pair<int, int> Shape = Find_Partner(Idx , Pos, Color);
        
        if (Shape.first == 1)
        {
            int n_Idx = Idx + 1;
            Area[n_Idx][i][Color] = Area[Idx][i][Color];
            Area[Idx][i][Color] = 0;
        }
        else if (Shape.first == 2)
        {
            int P_Idx = Idx + dx[Shape.second];
            int P_Pos = Pos + dy[Shape.second];
            if (Color == 0)
            {
                int Standard_Idx = Max(P_Idx, Idx);
                int Partner_Idx = Min(P_Idx, Idx);
                int n_Idx = Standard_Idx + 1;
                int nP_Idx = Partner_Idx + 1;
                Area[n_Idx][i][Color] = Area[Standard_Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[Partner_Idx][i][Color];
                Area[Partner_Idx][i][Color] = 0;
            }
            else
            {
                int n_Idx = Idx + 1;
                int nP_Idx = P_Idx + 1;
                Area[n_Idx][i][Color] = Area[Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[P_Idx][i][Color];
                Area[Idx][i][Color] = 0;
                Area[P_Idx][i][Color] = 0;
            }
        }
        else
        {
            int P_Idx = Idx + dx[Shape.second];
            int P_Pos = Pos + dy[Shape.second];
            if(Color == 0)
            { 
                int n_Idx = Idx + 1;
                int nP_Idx = P_Idx + 1;
                Area[n_Idx][i][Color] = Area[Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[P_Idx][i][Color];
                Area[Idx][i][Color] = 0;
                Area[P_Idx][i][Color] = 0;
            }
            else
            {
                int Standard_Idx = Max(Idx, P_Idx);
                int Partner_Idx = Min(Idx, P_Idx);
                int n_Idx = Standard_Idx + 1;
                int nP_Idx = Partner_Idx + 1;
                Area[n_Idx][i][Color] = Area[Standard_Idx][i][Color];
                Area[nP_Idx][i][Color] = Area[Partner_Idx][i][Color];
                Area[Partner_Idx][i][Color] = 0;
            }
        }
    }
    Move(Index - 1, Color);
}
 
void Remove_Full_Block()
{
    bool Flag = false;
    for (int Color = 0; Color < 2; Color++)
    {
        for (int i = 4; i < 10; i++)
        {
            int Cnt = 0;
            for (int j = 0; j < 4; j++)
            {
                if (Area[i][j][Color] == 0) break;
                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 i = 4; i < 6; i++)
        { 
 
            for (int j = 0; j < 4; j++)
            {
                if (Area[i][j][Color] == 0) continue;
                Cnt++;
                break;
            }
        }
 
        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;
}