4740. 밍이의 블록게임(D5)

2048게임과 비슷하다고 보면된다.

블록을 왼쪽, 오른쪽, 아래, 위로 이동시키면서 조건에 맞게 움직이는 시뮬레이션이다.

나는 문제 조건에 맞게 동작하도록 전부 반복문을 사용하였더니 다른사람들과 비교하여 6배정도 느린 속도가 나왔다.

연속된 칸을 계산할 때나, 좀더 시간을 줄일 방법을 찾아보면 조금은 더 줄일 수 있을 것 같긴 하다.

#include <stdio.h>
#include <string.h>
#include <memory.h>
 
char map[35][35]; //블록의 현재 상태를 저장하는 변수
char visit[35][35]; //가장 큰 값을 계산할 때, 계산된 블록인지 체크하는 변수
int value[35][35]; //해당 블록들의 값을 가지고 있는 변수
int n, m, q;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int sum;
 
void down()//map에서 아래 빈공간을 없애는 함수
{
    for (int i = 0; i < m; i++)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            if (map[j][i] == '#')
            {//빈공간이 있으면 그 다음칸부터 블록이 있는 칸을 찾아서 옴김
                for (int k = j - 1; k >= 0; k--)
                {
                    if (map[k][i] != '#')
                    {
                        map[j][i] = map[k][i];
                        map[k][i] = '#';
                        j--;
                    }
                    else if(k==0)
                    {//전부 빈공간이면 탐색할 필요가 없음
                        j = 0;
                    }
                }
            }
        }
    }
}
 
void left()//map에서 왼쪽으로 정렬
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == '#')
            {
                for (int k = j + 1; k < m; k++)
                {
                    if (map[i][k] != '#')
                    {
                        map[i][j] = map[i][k];
                        map[i][k] = '#';
                        j++;
                    }
                    else if (k == m - 1)
                    {
                        j = m;
                    }
                }
            }
        }
    }
}
 
void right()//map에서 오른쪽으로 정렬
{
    for (int i = 0; i < n; i++)
    {
        for (int j = m - 1; j >= 0; j--)
        {
            if (map[i][j] == '#')
            {
                for (int k = j - 1; k >= 0; k--)
                {
                    if (map[i][k] != '#')
                    {
                        map[i][j] = map[i][k];
                        map[i][k] = '#';
                        j--;
                    }
                    else if (k == 0)
                    {
                        j = 0;
                    }
                }
            }
        }
    }
}
 
void count(int x, int y)//연속된 블록 개수 
{
    sum++;
    for (int i = 0; i < 4; i++)
    {
        if (visit[x + dx[i]][y + dy[i]] == 0 && map[x + dx[i]][y + dy[i]] == map[x][y])//방문안했고 같은 색이면
        {
            visit[x + dx[i]][y + dy[i]] = 1;
            count(x + dx[i], y + dy[i]);
        }
    }
}
int main(void) {
    int T;
    setbuf(stdout, NULL);
    scanf("%d\n", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        memset(value, 0, sizeof(value));
        scanf("%d %d %d\n", &n, &m, &q);
        for (int i = 0; i < n; i++)
        {
            fgets(map[i], 35, stdin);
        }
 
        for (int z = 0; z < q; z++)
        {
            char op[10];
            scanf("%s", op);
            char check = 0;
            switch (op[0]) {
            case 'U':
                char next[35];
                
                fgets(next, 35, stdin);
                for (int i = 0; i < m; i++)
                {
                    if (map[0][i] != '#')//맨 위 블록이 하나라도 채워져있으면 못올림
                    {
                        check = 1;
                        break;
                    }
                }
                if (check)
                    break;
                //빈공간이 있으면 모든 블록을 한칸 위로 올림
                for (int i = 0; i < n - 1; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        map[i][j] = map[i + 1][j];
                    }
                }
                //맨 아래에 새로 입력된 블록 추가
                for (int i = 0; i < m; i++)
                {
                    map[n - 1][i] = next[i + 1];
                }
                down();//빈공간 없앰
                break;
            case 'L':
                left();
                break;
            case 'R':
                right();
                break;
            case 'D':
                int max = 0;
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        if (value[i][j] == 0 && map[i][j] != '#')//아직 선성된 값이 없으면 
                        {
                            sum = 0;
                            visit[i][j] = 1;
                            count(i, j);
                            int cnt = 0;
                            for (int a = 0; a < n; a++)
                            {
                                for (int b = 0; b < m; b++)
                                {
                                    if (visit[a][b] == 1)
                                    {
                                        value[a][b] = sum;
                                        cnt++;
                                    }
                                }
                                if (cnt == sum)
                                    break;
                            }
                            memset(visit, 0, sizeof(visit));
                            if (sum > max)
                                max = sum;
                        }
                    }
                }
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        if (value[i][j] == max)
                        {
                            map[i][j] = '#';
                        }
                    }
                }
                down();
                memset(value, 0, sizeof(value));
                break;
            }
        }
        printf("#%d\n", test_case);
        for (int i = 0; i < n; i++)
            printf("%s", map[i]);
        if (test_case != T)
            printf("\n");
    }
    return 0;
}