4740. 밍이의 블록게임

4740. 밍이의 블록게임

시간을 꽤나 써버린 문제이다. 기본적으로 시뮬레이션 문제에, 블록 최대 크기를 구하는 부분에서는 DFS문제를 이용했다.

U,L,R,D 이 네가지 경우로 케이스를 나누어서 문제를 풀었다.

U 같은 경우에는 일단 check() 함수를 통해서 배열의 맨 상단의 한줄이 비어있는지 확인하는데 사용했다. 만약 비어있다면 새로운 줄을 추가 

할 수 있다는 것이고, 그렇지 않다면 새로운 줄을 추가할 수 없다. 처음에 이 부분에서 실수한 점은 맨 처음에는 can_add 라는 변수를 쓰지 않고 check() 함수를 두번 호출했는데, 그럴경우 처음 호출에서는 true 가 나왔음에도 두번째 check() 함수에서는 MOVE_UP() 함수를 통해서 밑에 한줄을 추가해서 두번째 check() 함수에서는 false 값이 나올 수 있다는 점이었다. 그래서 이부분을 수정하고, 모든 칸을 아래로 옮기는 방식은 for문 2개와 while 문을 이용해서 구현하였다.

L , R 의 경우는 비슷한 경우였는데, 왼쪽이나 오른쪽으로 밀고 빈 공간이 생겼을 수 있기 때문에 아래로 밀어줘야했다. 처음에 문제를 풀 때 그냥 왼쪽, 오른쪽으로 한번만 밀었는데, 이 경우에는 빈 공간이 또 생길 수 있기 때문에 아래로 밀어줘야 했다.

D 같은 경우에는 처음 DFS를 이용해서 각 덩어리의 최대 크기를 구하였다. 그리고 그 최대값을 변수 M에 저장하였다. 그리고 map_num 에는 각 덩어리들의 크기를 덩어리 중 하나에 넣었다. 그래서 두번째 DFS에서는 map_num 과 최대값인 M인 같은 지역을 DFS를 돌려서 모두 빈 공간으로 만들어주는 작업을 실행했다. 그리고 그 후에는 아래로 밀어서 빈 공간을 없애는 방식으로 문제를 풀었다. 문제를 풀면서 자꾸 놓쳤던 부분은 , 맵의 크기가 N * M 이기 때문에 N,M 을 자꾸 구분하지 않고 M을 N으로 쓰는 실수가 많았다. 그러다보니 디버깅 과정에서 자꾸 눈에 보이지 않았다. 조금만 더 신경을 써서 이런 실수를 줄여야겠다. 

<정답 코드>

#include<iostream>
 
#define MAX 31
 
using namespace std;
int n, m, q;
char map[MAX][MAX];
int map_num[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void init()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
 
            visited[i][j] = false;
        }
    }
}
 
void MOVE_UP()
{
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != '#')
                map[i - 1][j] = map[i][j];
        }
    }
}
 
void dfs(int x,int y,char c,int* cnt,int M,bool erase)
{
 
    (*cnt)++;
    visited[x][y] = true;
    
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && map[nx][ny] == c)
        {
 
            dfs(nx, ny, c, cnt, M, erase);
        }
    }
 
    if (erase)
        map[x][y] = '#';
 
 
}
 
bool check()
{
    for (int i = 0; i < n; i++)
    {
        if (map[0][i] != '#')
            return false;
    }
 
    return true;
    
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++) {
        
        init();
        cin >> n >> m >> q;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> map[i][j];
            }
        }
 
 
        for (int i = 0; i < q; i++)
        {
            
            char cs;
            cin>>cs;
            if (cs == 'U') {
 
                bool can_add = false;
                if (check()) {
                    MOVE_UP();                    // 모든 줄 위로 한칸씩 땡겨서 아랫줄 비우기
                    can_add = true;
                }                                
                
                                        
                // 맨 아래칸 채우기
                for (int j = 0; j < m; j++) {
                    char tmp;
                    cin >> tmp;
                    if (can_add) {                // 맨 아랫줄 추가할 수 있는지 확인
                        map[n - 1][j] = tmp;    // 맨 아랫줄 추가
                    }
                }
                
                // 아래로 밀기
 
                for (int b = 0; b < m; b++) {
                    for (int a = n - 1; a >= 0; a--) {
 
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x + 1 >= 0 && y >= 0 && x + 1 < n && y < m && map[x + 1][y] == '#')
                            {
                                map[x][y] = '#';
                                map[x + 1][y] = c;
                                x++;
                            }
                        }
                    }
                }
            
            }
            else if (cs == 'L') {
 
                // 왼쪽으로 밀기
 
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < m; b++) {
                    
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x >= 0 && y-1 >= 0 && x < n && y-1 < m && map[x][y-1] == '#')
                            {
                                map[x][y] = '#';
                                map[x][y-1] = c;
                                y--;
                            }
                        }
                    }
                }
 
                // 아래로 밀기
 
                for (int b = 0; b < m; b++) {
                    for (int a = n - 1; a >= 0; a--) {
 
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x + 1 >= 0 && y >= 0 && x + 1 < n && y < m && map[x + 1][y] == '#')
                            {
                                map[x][y] = '#';
                                map[x + 1][y] = c;
                                x++;
                            }
                        }
                    }
                }
 
            }
            else if (cs == 'R') {
                
                // 오른쪽 밀기
 
                for (int a = 0; a < n; a++) {
                    for (int b = m-1; b >= 0; b--) {
 
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x >= 0 && y+1 >= 0 && x < n && y+1 < m && map[x][y + 1] == '#')
                            {
                                map[x][y] = '#';
                                map[x][y + 1] = c;
                                y++;
                            }
                        }
                    }
                }
 
                // 아래로 밀기
 
                for (int b = 0; b < m; b++) {
                    for (int a = n - 1; a >= 0; a--) {
 
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x + 1 >= 0 && y >= 0 && x + 1 < n && y < m && map[x + 1][y] == '#')
                            {
                                map[x][y] = '#';
                                map[x + 1][y] = c;
                                x++;
                            }
                        }
                    }
                }
                
            }
            else if (cs == 'D') {
                
                
                int M = 0;    // 가장 큰 덩어리 크기
 
                // visited 초기화
                for (int i = 0; i < MAX; i++)
                {
                    for (int j = 0; j < MAX; j++)
                    {
                        visited[i][j] = false;
                        map_num[i][j] = 0;
                    }
                }
 
                // dfs로 가장 큰 덩어리 MAX값 찾기
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < m; b++) {
                        if (map[a][b] != '#' && !visited[a][b])
                        {
                            int cnt = 0;
                            dfs(a, b, map[a][b],&cnt, M, false);
                            map_num[a][b] = cnt;
                            if (cnt > M)
                                M = cnt;
 
                        }
                    }
                }
 
                // visited 초기화
                for (int i = 0; i < MAX; i++)
                {
                    for (int j = 0; j < MAX; j++)
                    {
                        visited[i][j] = false;
                    }
                }
 
                // MAX값을 갖는 덩어리 없애기
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < m; b++) {
                        if (map_num[a][b]==M)
                        {
                            int cnt;                                // 필요없음
                            dfs(a, b, map[a][b], &cnt, M,true);        // 덩어리 큰 값들 삭제하기
                        }
                    }
                }
 
                // 아래로 밀기
 
                for (int b = 0; b < m; b++) {
                    for (int a = n - 1; a >= 0; a--) {
 
                        if (map[a][b] != '#') {
                            int x = a, y = b;
                            int c = map[a][b];
                            while (x + 1 >= 0 && y >= 0 && x + 1 < n && y < m && map[x + 1][y] == '#')
                            {
                                map[x][y] = '#';
                                map[x + 1][y] = c;
                                x++;
                            }
                        }
                    }
                }
 
                
            }
        }
 
        cout << "#" << t << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << map[i][j];
            }
            cout << endl;
        }
        cout << endl;
 
    }
 
    return 0;
}