백준) 11559 Puyo Puyo

Puyo Puyo

https://www.acmicpc.net/problem/11559

복잡한 구현의 문제.

우리가 아는 바로 그 게임을 구현하면 된다.

주의할 점은 현재 상태에서 4개이상 붙어버린 뿌요들은 한 번에 터지고(콤보 1),

한 번에 바닥으로 내려가고, 새로운 상태에서 새롭게 붙어버린 뿌요들도 한 번에 터진다는 것이다.

구현은 다음과 같이 하였다.

1. 맵을 DFS로 돌면서 현재 붙어버린 뿌요들을 파악한다.

2. 이 중 4개 이상되는 뿌요들만 한꺼번에 터진다.

3. 나머지 뿌요들이 바닥으로 내려오게 맵을 갱신해준다.

4. 1~3과정을 반복하면서 콤보 수를 센다.

과정 1을 수행하면서, 맵을 다른 곳에 기록해야 한다. DFS는 2개만 되어도 수행될 것이므로,

다른 곳에 좌표정보를 기록해두고, 과정 2에서 이를 써먹으면서 맵을 갱신해야 한다.

과정 3은 12*1의 배열이 6개 있다고 생각하고, 6개의 배열을 각각 갱신해주었다.

배열에서 뿌요들만 빼내서 다른 곳에 기록해두고, 배열을 갱신하는 방법을 사용했다.(스택 OR 큐)

코드로 옮기면 다음과 같다.

모든 과정을 수행하면서 맵 전체를 살피는게 불편하다면, 과정마다 뿌요들 중 최고 높이를 갱신하는 과정을 추가한다면

최적화가 가능해지지 않을까 생각한다.

#include <stdio.h>
#include <stack>
using namespace std;
 
typedef struct col {
    int x, y;
}col;
stack<col> st;
stack<int> st2;
 
int map[12][6];
int visit[12][6];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
char buf[8];
 
int dfs(int x, int y, int c) {
    int cnt = 1;
    visit[x][y] = c;
    st.push({ x,y });
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= 12 || yy >= 6)
            continue;
 
        if (map[xx][yy] == c && visit[xx][yy] == 0)
            cnt += dfs(xx, yy, c);
    }
    return cnt;
}
 
void arange() {
    for (int i = 0; i < 12; ++i)
        for (int j = 0; j < 6; ++j)
            visit[i][j] = 0;
 
    for (int i = 0; i < 6; ++i) {
        for (int j = 11; j >= 0; --j) {
            if (map[j][i] > 0) {
                st2.push({ map[j][i] });
                map[j][i] = 0;
            }
 
        }
        int cnt = 0;
        while (!st2.empty()) {
            map[cnt++][i] = st2.top();
            st2.pop();
        }
    }
}
 
int main() {
    for (int i = 11; i >= 0; --i) {
        scanf("%s", buf);
        for (int j = 0; j < 6; ++j) {
            if (buf[j] == 'R')
                map[i][j] = 1;
            else if (buf[j] == 'G')
                map[i][j] = 2;
            else if (buf[j] == 'B')
                map[i][j] = 3;
            else if (buf[j] == 'P')
                map[i][j] = 4;
            else if (buf[j] == 'Y')
                map[i][j] = 5;
        }
    }
 
    int combo = 0;
 
    while (1) {
        int del = 0;
        for (int i = 0; i < 12; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (map[i][j] > 0 && visit[i][j] == 0) {
                    int cnt = dfs(i, j, map[i][j]);
 
                    if (cnt >= 4) {
                        del += cnt;
 
                        while (!st.empty()) {
                            map[st.top().x][st.top().y] = 0;
                            st.pop();
                        }
                    }
                    else {
                        while (!st.empty())
                            st.pop();
                    }
 
                }
            }
        }
        if (del == 0)
            break;
 
        arange();
        combo++;
    }
    printf("%d", combo);
 
    return 0;
}