[BOJ] 11559. Puyo Puyo

Puyo Puyo

클릭시 이동합니다.

어떻게 풀까?

시뮬레이션문제입니다!

시뮬레이션 문제는 문제에서 요구하는 것들에 대해서 구조체와 함수를 잘 만들어야합니다!

해당 문제에서 요구하는 것은 크게 두 가지 입니다.

1. 상 하 좌 우로 4개의 블럭들이 모여있으면 터뜨려라!

2. 빈 공간이 생기면 아래로 내려라!

두 가지 모두 이전에 했던 밍이의 블록게임과 유사한 작업입니다.

만약, 글만으로 잘 이해가 안된다면, 해당 포스팅을 한번 보시는 것을 추천드립니다!

그럼 우선, 1번 작업에 대해 프로그래밍을 해봅시다.

우선, 맵을 다 보면서 블록이 있는지 확인합니다. 그리고, 만약 블록이 있다면,

아래 단계를 순서대로 실행합니다.

1. 블록의 상하좌우에 같은 블록이 있으면 큐에 담고, visit check를 해준다.

2. 블록의 좌표를 스택에 넣는다.

3. 큐가 비어있다면 빠져나온다.

4. 스택사이즈가 4보다 크면 해당 스택을 비운다.

그럼 이제, 2번 작업을 프로그래밍 해봅시다!

1열~6열까지 다음 아래 과정을 반복합니다!

1. 시작은 1행 부터 한다!

2. 1행 ~ 12행까지 살펴보면서 블록이 있다면 스택에 쌓는다.

3. 12행까지 닿았다면, 이제 12행부터 스택이 빌 떄까지 쌓였던 스택의 블록을 놓는다.

이렇게 하면 아래에서부터 넣었던 블록들이 순서대로 나타나겠죠!

그럼, 위 과정을 몇 번 반복해야할까요?

위 과정은 터뜨리는것이 없을때까지 반복해야합니다!

우선, 터진 개수를 카운트 하는 변수를 0으로 둡시다.

그리고, 터뜨리는 작업을 구현한 함수에서, bool을 return 하도록 합시다.

만약, 한 번이라도 터지는게 발생했다면 계속 실행합니다.

한 번도 터진 블록이 없으면 이제 카운트 값을 출력하고 프로그램을 종료하면 됩니다!

코드

//https://www.acmicpc.net/problem/5213/
// 뿌요뿌요
#include<cstdio>
#include<cstring>
char map[12][7];
 
char st[12], top;
bool visit[12][6];
 
int st2[100][2];
int que[100][2];
 
void down(){
    for(int j = 0; j < 6; j++){
        top = 0;
        for(int i = 0; i < 12 ; i++){
           if(map[i][j] != '.'){
               st[top++] = map[i][j];
               map[i][j] = '.';
           } 
        }
        int i = 11;
        while(top){
            map[i][j] = st[--top];
            i--;
        }
    }
}
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
bool bbang(int r, int c){
    char flag = map[r][c];
    int fr, re;
    fr = re = 0;
 
    que[re][0] = r;
    que[re++][1] = c;
    
    visit[r][c] = true;
    
    top = 0;
    st2[top][0] = r;
    st2[top++][1] = c;
 
    while(fr!=re){
       int now[2] = {que[fr][0], que[fr][1]};
       fr++;
 
        for(int d = 0; d < 4; d++){
            int next[2] = {now[0] + dr[d], now[1] + dc[d]};
 
            if(map[next[0]][next[1]] != flag) continue;
            if(visit[next[0]][next[1]]) continue;
            visit[next[0]][next[1]] = true;
 
            que[re][0] = next[0];
            que[re++][1] = next[1];
 
            st2[top][0] = next[0];
            st2[top++][1] = next[1];
        }
    }
 
    bool ret = false;
    if(top >= 4){
        ret = true;
        while(top){
            top--;
            map[st2[top][0]][st2[top][1]] = '.';
        }
    }
    return ret;
}
int main(){
    for(int i = 0; i < 12; i++){
           scanf("%s\n", map[i]); 
    }
 
    int res = 0;
    bool isEnd = false;
    while(!isEnd){
        isEnd = true;
        memset(visit, false, sizeof(visit));
        for(int i = 0; i < 12; i++){
            for(int j = 0; j < 6; j++){
                if(map[i][j] == '.') continue;
               isEnd &= !bbang(i,j); 
            }
        }
        down();
        res++;
    }
    printf("%d\n", --res);
    return 0;
}

여담

시간 복잡도는 어떻게 될까요!?

데이터의 입력 수가 따로 존재하지 않기 때문에

O(1)이라고 보셔도 되겠습니다!

(솔직히 쓰고나서도 조금 애매하네요 흠.. 굳이 따지자면 블록수를 N이라고 했을때 O(N) 이라는 것 정도네요!)