[ SWEA 4740 ] 밍이의 블록 게임 (C++)

SWExpertAcademy의 밍이의 블록게임(4740 / D5) 문제이다.

[ 문제풀이 ]

맵에 존재하는 블럭들을 명령어에 따라 움직이고 내리고 올리고 하는 과정을 구현해야 하는 문제이다.

지금부터는 본인이 구현한 방법을 명령어별로 소개하겠다.

특별한 알고리즘이나 방법이 사용되는 것이 아니기 때문에, 간략한 설명과 코드 설명을 함께 진행하겠다.

1. Command 'U'

입력으로 주어지는 한 행의 블록 배열을 가장 아랫줄에 추가해야 하는 명령어이다.

단 ! 추가되지 않는 딱 한가지 경우가 있다.

바로 "모든 행에 하나 이상의 블록이 존재하는 경우" 이다.

간단하게 말해서 맵이 0열 ~ M - 1열까지 존재한다고 가정했을 때, 그 어느 한 열이라도, 0번째 행에 블럭이 존재한다면

이는 가장 윗줄에 블럭이 존재한다는 것을 의미하고, 더 이상 블록 배열을 가장 아랫줄에 추가할 수 없다는 것을

의미한다.

따라서, 위의 경우는 해당 명령을 무시하고 진행하면 된다.

void Up(string NewLine)
{
    for (int i = 0; i < M; i++)
    {
        if (MAP[0][i] != '#') return;
    }
    
    for (int i = 1; i < N; i++) memcpy(MAP[i - 1], MAP[i], sizeof(char)* M);
    for (int i = 0; i < M; i++) MAP[N - 1][i] = NewLine[i];
}

본인이 구현한 명령어 'U' 소스코드이다.

line3 ~ 6)을 보면, 모든 열을 탐색하면서, 0번행에 블럭이 있는 열이 하나라도 있다면, 명령어를 진행시키지 않고 그대로 return 시킴으로써 종료시키는 것을 확인할 수 있다.

그게 아니라면, 모든 행에 존재하는 블럭들을 한 줄씩 올려주면 된다. 이 과정이 line8) 에 있는 과정이다.

line9) 에서는 추가되는 새로운 행을 가장 마지막 행에 추가해주는 과정이다.

그런데 ! 이렇게 하면 새로운 행을 추가하고, 모든 블럭들을 한칸 위로 옮기는 과정을 진행하는 것은 맞지만, 새로운 행에 빈 칸이 있을 경우, 그 빈칸에 맞게 블럭들을 다시 떨궈줘야 하는 과정또한 진행해 주어야 한다.

이 과정은, 'D'명령어에서도 사용되기 떄문에, 다른 명령어들을 모두 소개한 후에 마지막에 설명하겠다.

2.  Command 'L' & 'R'

블럭들을 왼쪽으로, 혹은 오른쪽으로 옮겨야 하는 명령어이다.

똑같은 방법으로 구현해서 2개의 명령어를 하나로 묶어서 설명하겠다.

void Left()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < M; j++)
        {
            if (MAP[i][j] == '#') continue;
            
            int ny = j - 1;
            while (ny >= 0 && MAP[i][ny] == '#') ny--;
            ny++;
            
            if (ny != j)
            {
                MAP[i][ny] = MAP[i][j];
                MAP[i][j] = '#';
            }
        }
    }
}
 

본인이 구현한 명령어 'L'에 대한 코드이다.

블럭이 존재하는 좌표를 찾게 되면 움직일 수 없을 떄 까지 빈칸을 찾아서 계속해서 움직여 준다.

이 과정이 line10)에 나타나 있다. 움직일 수 없을 때 까지 반복하면서 좌표를 갱신해준다.

그래서 더 이상 움직일 수 없는 좌표를 찾았다면, 2가지 경우가 발생한다.

1. 애초에 움직일 수 없는 블럭이었는지

2. 움직일 수 있는 블럭이었는지

만약, 애초에 움직일 수 없는 블럭이었다면, "움직일 수 없을 때 까지 반복한 좌표가 기존의 좌표와 동일" 할 것이다.

그럼, 블럭의 갱신이 필요하지 않다.

반대로, 움직일 수 있는 블럭이라면, line13)과 같이 조건문에 부합해서 블럭의 갱신이 일어나게 된다.

3. Command 'D'

가장 크기가 큰 블록 집합을 없애야 하는 명령어 이다.

이 과정을 본인은 BFS탐색을 통해서 그 갯수를 파악해 주었다.

또한, 갯수를 파악하면서 동시에 "어떤 집합을 삭제해야 되는지"를 표현하기 위해서 Visit배열을 사용해 주었다.

Visit배열을 단순, true / false가 아닌, 1번부터 번호를 매기면서 탐색을 해주었다.

void Down()
{
    vector<int> V;
    memset(Visit, 0, sizeof(Visit));
    int Num = 1;
    int Max_Block = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == '#') continue;
            if (Visit[i][j] != 0) continue;
            
            int Result = BFS(i, j, MAP[i][j], Num);
            if (Result > Max_Block)
            {
                Max_Block = Result;
                V.clear();
                V.push_back(Num);
            }
            else if (Result == Max_Block)
            {
                V.push_back(Num);
            }
            Num++;
        }
    }
 
    for (int i = 0; i < V.size(); i++) Erase(V[i]);
}

4. 맵 정리하기

''U'명령어 혹은 'D'명령어 이후에는 맵을 재정리를 해줄 필요가 있다. 왜냐하면 중간중간 빈 공간이 존재할 수 있기 때문이다.

이 과정 또한, 위에서 설명한 'L' 과 'R'명령어와 동일한 방법으로 구현해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
#define endl "\n"
#define MAX 35
using namespace std;
 
int N, M, Q;
int Visit[MAX][MAX];
char MAP[MAX][MAX];
vector<pair<char, string>> Cmd;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Print()
{
    for (int i = 0; i < N; i++)
    {
        cout << MAP[i] << endl;
    }
}
 
void Initialize()
{
    Cmd.clear();
    memset(Visit, 0, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> M >> Q;
    for (int i = 0; i < N; i++)
    {
        cin >> MAP[i];
    }
    for (int i = 0; i < Q; i++)
    {
        char C; cin >> C;
        if (C == 'U')
        {
            string S; cin >> S;
            Cmd.push_back(make_pair(C, S));
        }
        else Cmd.push_back(make_pair(C, ""));
    }
}
 
void Up(string NewLine)
{
    for (int i = 0; i < M; i++)
    {
        if (MAP[0][i] != '#') return;
    }
    
    for (int i = 1; i < N; i++) memcpy(MAP[i - 1], MAP[i], sizeof(char)* M);
    for (int i = 0; i < M; i++) MAP[N - 1][i] = NewLine[i];
}
 
void Left()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < M; j++)
        {
            if (MAP[i][j] == '#') continue;
            
            int ny = j - 1;
            while (ny >= 0 && MAP[i][ny] == '#') ny--;
            ny++;
            
            if (ny != j)
            {
                MAP[i][ny] = MAP[i][j];
                MAP[i][j] = '#';
            }
        }
    }
}
 
void Right()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = M - 2; j >= 0; j--)
        {
            if (MAP[i][j] == '#') continue;
 
            int ny = j + 1;
            while (ny < M && MAP[i][ny] == '#') ny++;
            ny--;
            
            if (ny != j)
            {
                MAP[i][ny] = MAP[i][j];
                MAP[i][j] = '#';
            }
        }
    }
}
 
int BFS(int a, int b, char C, int Num)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = Num;
    int Cnt = 1;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        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)
            {
                if (Visit[nx][ny] == 0 && MAP[nx][ny] == C)
                {
                    Visit[nx][ny] = Num;
                    Q.push(make_pair(nx, ny));
                    Cnt++;
                }
            }
        }
    }
    return Cnt;
}
 
void Erase(int Num)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Visit[i][j] == Num) MAP[i][j] = '#';
        }
    }
}
 
void Down()
{
    vector<int> V;
    memset(Visit, 0, sizeof(Visit));
    int Num = 1;
    int Max_Block = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == '#') continue;
            if (Visit[i][j] != 0) continue;
            
            int Result = BFS(i, j, MAP[i][j], Num);
            if (Result > Max_Block)
            {
                Max_Block = Result;
                V.clear();
                V.push_back(Num);
            }
            else if (Result == Max_Block)
            {
                V.push_back(Num);
            }
            Num++;
        }
    }
 
    for (int i = 0; i < V.size(); i++) Erase(V[i]);
}
 
void Arrange_MAP()
{
    for (int i = N - 2; i >= 0; i--)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == '#') continue;
            
            int nx = i + 1;
            while (nx < N && MAP[nx][j] == '#') nx++;
            nx--;
 
            if (nx != i)
            {
                MAP[nx][j] = MAP[i][j];
                MAP[i][j] = '#';
            }
        }
    }
}
 
void Solution()
{
    int Idx = 0;
    for (int i = 0; i < Q; i++)
    {
        char Command = Cmd[i].first;
        if (Command == 'U') Up(Cmd[i].second);
        else if (Command == 'L') Left();
        else if (Command == 'R') Right();
        else Down();
 
        Arrange_MAP();
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << endl;
        Print();
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}