백준 #11559 / 뿌요뿌요(Puyo Puyo)

문제

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 잇는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

입력

12*6의 문자가 주어진다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.(모두 대문자로 주어진다.)

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태(즉 뿌요 아래에 빈 칸이 있는 경우는 없음) 이다.

출력

현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.)

---

문제 조건 빼먹어서 처음부터 다시 풀었다. 2시간 걸렸다 ㅜㅠㅠ반성해야지...

[How To Solve?]

- 실제 뿌요뿌요 게임처럼, 4개 이상 연결돼있으면 뿌시면된다.

- 가장 먼저, 맵에서 뿌요가 있는 부분은 BFS로 돌아준다.

- BFS로 돌면서 뿌요의 갯수를 세어주는데, 4개 이상이면 check배열에 1로 표시해준다.(부셔야 한다는 의미)

- 4개 미만이라면, check배열에 2로 표시해준다.(파괴 불가능, 방문할 필요 없음을 의미)

- 4개 이상이 하나라도 생기면, replay를 1로 만들어준다. 가장 중요한 부분인데, 실제 게임처럼 4개이상 뭉쳐져 있는 무리가 한 꺼번에 터진다는 점을 유의해야 한다. 안그러면 틀림..

- replay가 1이라면, 연쇄의 횟수를 추가해주고, 그 이외의 값이라면 터진 것이 하나도 없었다는 의미가 되므로 replay를 2로 만들어주면서 빠져나간다.

- 가장 핵심!! temp[12]배열에 각 줄을 갱신해준다.

1) check배열에서 2인 것만 골라서 temp배열의 뒤에서부터 집어 넣어주고

2) 나머지 값은 죄다 점으로 만들어서 저장해준 뒤

3) temp배열로 MAP의 해당 줄을 갱신해준다. 6번 반복

[Code]

#include<iostream>
#include<queue>
#define P pair<int,int>
#define MP(a,b) make_pair(a,b)
using namespace std;
 
int totalcnt;
char MAP[12][6];
int check[12][6];    // 0 : 방문 안함, 1 : 뿌셔야됨, 2 : 뿌실 필요 없음.
char temp[12];
int replay;
int xx[] = { -1,1,0,0 };
int yy[] = { 0,0,-1,1 };
 
void bfs(int, int);
void init_check(void);
void REMAP(void);
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
 
    for (int i = 0; i < 12; i++) 
        for (int j = 0; j < 6; j++) 
            cin >> MAP[i][j];
 
    while (replay!=2) {
        replay = 0;
        init_check();
        for (int i = 11; i >= 0; i--) {
            for (int j = 0; j < 6; j++) {
                if (MAP[i][j] != '.' && check[i][j]==0) {
                    bfs(i, j);    // .도 아니고 방문한 지점도 아니면 bfs 돌아준다.
                }
            }
        }
        REMAP();
        if (replay == 1) totalcnt++;    // 다 돌았을 때 한 번이라도 터졌으면 연쇄횟수를 늘린다.
        else if (replay == 0) replay = 2;    // replay값이 변하지 않았다면, 터진것이 없으므로 빠져나간다.
    }
    printf("%d\n", totalcnt);
    return 0;
}
void showMap(void) {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++)
            printf("%c", MAP[i][j]);
        printf("\n");
    }
}
void bfs(int x, int y) {
    int cnt = 0;
 
    queue<P> Q;
    queue<P> SQ;
    Q.push(MP(x, y));
    SQ.push(MP(x, y));
 
    char color = MAP[x][y];
    check[x][y] = true;
    cnt++;
 
    while (!Q.empty()) {
        int cx = Q.front().first;
        int cy = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = cx + xx[i];
            int ny = cy + yy[i];
            if (nx < 0 || ny < 0 || nx >11 || ny >5) continue;    // 맵 벗어나면 무시
            if (check[nx][ny]) continue;    // 방문한 지점이면 무시
            if (MAP[nx][ny] == color) {    // 같은 컬러라면
                cnt++;    // 뿌요갯수 증가
                check[nx][ny] = true;    // 방문한 것으로 처리
                Q.push(MP(nx, ny));
                SQ.push(MP(nx, ny));
            }
        }
    }
    // 여기까지 진행하면 BFS 돌면서 좌표가 저장돼있음.
    if (cnt < 4) {
        while (!SQ.empty()) {
            check[SQ.front().first][SQ.front().second] = 2;
            SQ.pop();
        }
        return;    // 뿌요의 갯수가 4개 미만이라면 뿌실수 없음
    }
    else replay = 1;    // 뿌요의 갯수가 4개 이상이라면 뿌수고 다시 bfs 돌아야 하므로 true로 전환
}
 
void init_check(void) {
    for (int i = 0; i < 12; i++) 
        for (int j = 0; j < 6; j++) 
            check[i][j] = 0;
}
 
void REMAP(void) {
    for (int i = 0; i < 6; i++) {
        int idx = 11;
        for (int j = 11; j >=0; j--) {
            if (check[j][i] == 2) 
                temp[idx--] = MAP[j][i];
            else if (check[j][i] == 0) break;
        }
        while (idx >= 0) temp[idx--] = '.';
        for (int k = 0; k < 12; k++)
            MAP[k][i] = temp[k];
    }
}