[백준] 11559번 Puyo Puyo

11559 Puyo Puyo

문제

---

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

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

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

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

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

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

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 

하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

입력

---

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

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

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

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

출력

---

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

---

풀이)

간단할 줄 알았는데 몇가지를 간과해서 3번째 시도 끝에 맞은 문제이다.

내가 작성한 코드의 과정은 이러하다.

1. 맨왼쪽, 맨아래쪽 칸부터 bfs를 통해 같은 색이 4개 이상 있는지 확인한다.(이는 모든 칸에 수행한다.)

 1.1 만일 있다면 이를 없애준다.

 1.2 없다면 다음 열에 가서 1을 반복한다. (이 때, 이미 이전에 방문했던 뿌요라면 pass)

2. 뿌요들을 아래로 내려준다.

간단하지만, 여러 이유때문에 틀렸었다.

주의할 점을 말해보자면

1) 터질 수 있는 뿌요가 여러 그룹이라면 한번에 터트려야 한다는 점. 

    (이 조건을 처음에 못봐서 터트릴때마다 횟수를 늘렸었다.)

2) 터트린 후 중간중간 뿌요들 사이에 공백이 있을 수 있다는 점.

2번째 주의할 점을 그림으로 보자면 이러하다.

. . . . . .                                 . . . . . .

.B . . . .                                 . . . . . .

. . . . . .                                 . . . . . .

. . . . . .         → 내릴 경우        . . . . . .

.B . . . .                                 . B . . . .

.B B . . .                                . B . . . .

. . . . . .                                 . B . . . .

RB . . . .                                RBB . . .

이런식으로 나와야하는데 처음에 노란색 부분만 공백 처리를 해줘서 틀렸었다.

(마지막 행에 있는 뿌요만 터지는게 아니라는 것을 간과)

맨 아래 행만 확인해서는 안되고, 뿌요들을 아래로 내릴때 모든 칸을 반복해서 다 확인해야 한다.

코드)

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
char map[12][6];
int result;
bool visited[12][6];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue <pair<int, int>> qu;
vector <pair<int, int>> puyo;
 
void bfs(int a,int b) {
    qu.push({ a,b });
    visited[a][b] = true;
    char ch = map[a][b];
 
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        for (int j = 0; j < 4; j++) {
            int ny = y + dy[j];
            int nx = x + dx[j];
            if (ny >= 0 && ny < 12 && nx >= 0 && nx < 6) {
                if (visited[ny][nx] || map[ny][nx] != ch) continue;
                visited[ny][nx] = true;
                qu.push({ ny, nx });
                puyo.push_back({ ny,nx });
            }
        }
    }
}
 
int main() {
 
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            scanf("%c", &map[i][j]);
        }
        getchar();
    }
    
    while (true)
    {
        //연쇄할게 더는 없어 게임을 종료시키는 bool
        bool finish = true;
 
        //맨 밑바닥의 열들부터 확인
        for (int i = 11; i >= 0; i--) {
            for (int j = 0; j < 6; j++) {
                if (visited[i][j] || map[i][j] == '.') continue; //이전에서 이미 확인한 곳이면 pass
                bfs(i, j);
                //연쇄가 일어날 수있다면
                if (puyo.size() >= 3) {
                    puyo.push_back({ i,j });
                    finish = false;    
                    for (int i = 0; i < puyo.size(); i++) {
                        map[puyo[i].first][puyo[i].second] = '.';
                    }
                }
                puyo.clear();
            }
        }
        
        //연쇄가 일어날수 없다면 종료
        if (finish) break;
 
        //연쇄한 후 아래로 떨어뜨림
        for (int i = 11; i > 0; i--) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] == '.'&&map[i - 1][j] != '.') {
                    map[i][j] = map[i - 1][j];
                    map[i - 1][j] = '.';
                    i = 12;
                    break;
                }
            }
        }
 
        //다음 확인을 위해 visited초기화
        for (int i = 0; i < 12; i++) {
            fill(visited[i], visited[i] + 6, false);
        }
        result++;
    }
    printf("%d", result);
    return 0;
}

결과)