[C++] 백준 - 11559 : Puyo Puyo

문제 링크

11559번: Puyo Puyo

 

 

풀이 )

• puyo( ): 터지는지 여부
• dfs( ): puyo( )에서 연속된 4개의 블록이 있는지 확인하기 위한 재귀함수
• pung( ): 4개 이상의 블록이 붙어있는 경우 같은 종류의 블록을 모두 터뜨림
• fall( ): 블록 아래로 내리기

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> field(12);
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void fall(){
    for(int c = 0; c < 6; ++c){
        for(int r = 11; r > 0; --r){
            while(field[r][c] == '.'){
                int flag = true;
                for(int i = r; i > 0; --i){
                    if(field[i][c] != '.')
                        flag = false;
                    field[i][c] = field[i-1][c];
                }
                if(flag){
                    if(field[0][c] == '.')
                        break;
                }
                field[0][c] = '.';
            }
        }
    }
}

void pung(int x, int y, char c){
    field[x][y] ='.';
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6)
            continue;
        if(field[nx][ny] == c)
            pung(nx, ny, c);
    }
    return;
}

int dfs(int x, int y, char c, vector<vector<bool> > visited){
    int ret = 1;
    visited[x][y] = true;
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || visited[nx][ny])
            continue;
        if(field[nx][ny] == c)
            ret += dfs(nx, ny, c, visited);
        if(ret >= 4)
            break;
    }
    return ret;
}

bool puyo(){
    bool ret = false;
    vector<vector<bool> > visited(12, vector<bool>(6));
    for(int r = 0; r < 12; ++r){
        for(int c = 0; c < 6; ++c){
            if(field[r][c] == '.' || visited[r][c])
                continue;
            if(dfs(r, c, field[r][c], visited) < 4)
                continue;
            pung(r, c, field[r][c]);
            ret = true;
        }
    }
    return ret;
}

int main(void){
    for(int i = 0; i < 12; ++i)
        cin >> field[i];

    int ans = 0;
    while(1){
        if(!puyo()){
            cout << ans << '\n';
            return 0;
        }
        ans++;
        fall();
    }
}

 

주의)

• puyo( )에서 dfs( )의 결과가 4가 넘어가면 바로 재귀함수를 호출할 필요없이 터뜨리기 때문에 바로 continue 처리해준다.(안해주면 시간초과)
• 터뜨릴때는 한번에
• 떨어뜨리는 부분에서 실수가 많이 일어나는 편이다.