[백준] 11559번 Puyo Puyo (C++)

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

 

 

이 문제는 푸요푸요라는 게임이라는 것을 했을때 몇번 연속으로 터지는지 출력하는 문제이다.

총 5 종류의 푸요가 있고 이 푸요는 상하좌우로 4개 이상이어야지 없어진다.

 

따라서 푸요를 없애기 위해서는 하나의 기준 푸요를 잡았을때 상하좌우로 4개 이상인지 체크하고 4개 이상인 경우 빈칸으로 만들어 없애주는 과정이 필요하다. -> BFS사용

 

이후로 푸요가 아래에 붕 떠있을때 아래로 내려주는 과정이 필요하다. 이것은 아래에서부터 위로 탐색하여

만약 푸요가 있는 경우 리스트에 넣어준다 이후에 다시 아래에서부터 리스트에 처음들어온것부터 빼주어 푸요를 놓는다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char graph[13][7];
bool visited[13][7];
bool flag;
int cnts;

void bfs(int a, int b) {
    queue<pii> q;
    visited[a][b] = true;
    int cnt = 1;
    vector<pii> tmp;
    tmp.push_back({a, b});
    q.push({a, b});

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;

            if(!visited[nx][ny] && graph[nx][ny] == graph[x][y]) {
                q.push({nx, ny});
                tmp.push_back({nx, ny});
                visited[nx][ny] = true;
                cnt++;
            }
        }
    }

    if(cnt >= 4) {      // 없앨 수 있음
        flag = true;
        for(auto it : tmp) {
            int x = it.first;
            int y = it.second;

            graph[x][y] = '.';
        }
    }
}

void Print() {
    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 6; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

void down() {
    for(int j = 0; j < 6; j++) {
        vector<char> tmp;
        for(int i = 11; i >= 0; i--) {
            if(graph[i][j] != '.') tmp.push_back(graph[i][j]);
        }

        int idx = 11;

        for(auto it : tmp) {
            graph[idx--][j] = it;
        }

        for(int i = idx; i >= 0; i--) {
            graph[i][j] = '.';
        }
    }
}

void solve() {
    while(true) {
        memset(visited, 0, sizeof(visited));
        flag = false;
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 6; j++) {
                if(!visited[i][j] && graph[i][j] != '.') {
                    bfs(i, j);
                }
            }
        }
        // 아래로 이동
        down();

        if(!flag) {
            break;
        }
        cnts++;
    }
    cout << cnts;
}

void input() {
    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 6; j++) {
            cin >> graph[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();

    return 0;
}

 

 

회고록

푸요를 터뜨리는 과정은 굉장히 쉬웠다. 이후 푸요를 어떻게 떨어뜨려야되는지 너무 시간을 오래 사용한 것 같다.

단순히 스택을 사용하여 아래에서부터 탐색하면 될것을 너무 어렵게 생각하여

푸요에서부터 아래로 내려가면서 바꿔야 하나?? 라고 생각해서 시간이 오래 걸렸다.