BOJ 11559 - Puyo Puyo

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

BFS, DFS 둘 중 하나를 선택해서 4개 이상 나오는 뿌요를 제거하고 

제거된 뿌요 위에 올라가 있는 뿌요가 하나 이상 있으면 그 뿌요들을 바닥으로 내리는 작업을 수반해야하는 문제다.

BFS 를 통해서 4개 이상 나오는 뿌요와 이를 제거하고 바닥으로 내리는 것 까지는 했으나,

동시에, 4개 이상 존재하는 뿌요의 집단군이 여러개 있을때, 이를 모두 제거하고 카운팅 했어야했는데

이를 못해서 통과를 못하고 있었다 (동시에 처리를 못하면 18% 정도에서 틀렸습니다 나옴)

 

아래 내용을 보고 겨우 해답을 이해할 수 있었다

pangtrue.tistory.com/117

[백준 11559 : C++] Puyo Puyo / BFS, DFS

 

 

- C++

 

#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int answer;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
char adj[12][6];                // 인접행렬
bool visited[12][6];            // 방문여부 행렬
int labelingAdj[12][6];         // 동일한 색상의 뿌요에는 동일한 label 번호가 붙는다.
int labelingCount[12 * 6 + 1];  // label 번호가 몇개 들어있는지 파악하고, 4개 이상 있으면 지워야할게 있는것.
 
void resetPuyo() {
    for (int c = 0; c < 6; ++c) {
        int row_top = 11;
        for (int r = 11; r >= 0; --r) {
            if (adj[r][c] == '.') continue;
            if (row_top != r) {
                adj[row_top][c] = adj[r][c];
                adj[r][c] = '.';
            }
            --row_top;
        }
    }
}
 
void removePuyo(int label) {
    for (int i = 1; i <= label; ++i) {
        if (labelingCount[i] >= 4) {
            for (int y = 0; y < 12; ++y) {
                for (int x = 0; x < 6; ++x) {
                    if (labelingAdj[y][x] == i)
                        adj[y][x] = '.';
                }
            }
        }
    }
}
 
void bfs(int r, int c, int label) {
    char color = adj[r][c];
    queue<pair<int, int>> q;
    q.push(make_pair(r, c));
    visited[r][c] = true;
    labelingAdj[r][c] = label;
    labelingCount[label]++;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || ny >= 12 || nx < 0 || nx >= 6) continue;
            if (!visited[ny][nx] && adj[ny][nx] == color) {
                q.push(make_pair(ny, nx));
                visited[ny][nx] = true;
                labelingAdj[ny][nx] = label;
                labelingCount[label]++;
            }
        }
    }
}
 
bool canDeletePuyo(int label) {
    for (int i = 1; i <= label; ++i)
        if (labelingCount[i] >= 4) return true;
 
    return false;
}
 
int solve() {
    int label = 1;
    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (!visited[i][j] && adj[i][j] != '.') {
                bfs(i, j, label++);
            }
        }
    }
    return label;
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    for (int i = 0; i < 12; ++i)
        for (int j = 0; j < 6; ++j)
            cin >> adj[i][j];
 
    while (1) {
        memset(visited, false, sizeof(visited));
        memset(labelingAdj, 0, sizeof(labelingAdj));
        memset(labelingCount, 0, sizeof(labelingCount));
 
        int label = solve();
 
        if (!canDeletePuyo(label)) break;
 
        removePuyo(label);
 
        resetPuyo();
 
        answer += 1;
    }
 
    cout << answer << endl;
 
    return 0;
}