[C++/11559] puyo puyo - using simulation

11559 puyo puyo

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

 

solution

전형적인 시뮬레이션 문제이다.

여기서 포인트는 어떻게 "아래로 떨어짐"을 구현하는가 이다.

아래로 떨어지는 걸 구현하기 위해서는 가장 밑에 있는 뿌요가 없애야 하는 것인지 아닌지에 따라 다르다.

만약 가장 밑에 있는 뿌요가 없어져야 한다면 위에서부터 한칸씩 내려오면서 값을 덮어씌우고 마지막에 맨 첫 줄의 뿌요 값을 . 으로 교체해주면 된다.

알고리즘은 다음과 같다.

 

1. 현재 필드 값을 보고 BFS를 돌려 인접한 색의 개수가 4개인 그룹을 찾는다.

2. 이 그룹의 값들은 없어져야 하기 때문에 이를 표시하기 위해 좌표를 저장했다가 * 으로 바꾼다.

3. 없어져야 하는 값들에 대해서 for문을 돌면서 뿌요를 아래로 내린다.

4. 맨 밑의 뿌요가 없어져야 하는 값이라면 그 위의 행부터 0까지 하나씩 위의 값으로 덮어씌운다. 그 후 한번 더 체크하기 위해 for문의 반복 연산자를 원래대로 되돌린다. (+1)

 

한번 더 체크해야 하는 이유는 다음과 같은 케이스가 있기 때문이다.

ex.

RRYG

RRYG

 

이 경우 R이 4개로 터트릴 수 있기 때문에 없어져야 해서 BFS() 함수 후 모습은 다음과 같다.

**YG

**YG

 

이때 puyoDown() 함수 안에서 1번 for문을 실행한 후 모습은 다음과 같다.

..YG

**YG

 

즉 현재 보고 있는 행의 뿌요가 다시 *가 되는 경우가 있기 때문에 한번 더 검사해야 한다.

 

 

전체 코드

// 11159 Puyo Puyo

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

char map[12][16];			// 처음 뿌요 필드
bool visited[12][16];		// BFS 탐색 방문 처리 2차원 배열
int dx[4] = {1, -1, 0, 0};	// BFS 탐색 인접한 x
int dy[4] = {0, 0, 1, -1};	// BFS 탐색 인접한 y

// 1. BFS를 돌려 인접한 색의 그룹 구함
bool BFS(int startX, int startY) {
    char color = map[startX][startY];	// 현재 색
    int cnt = 0;
    
    queue<pair<int, int>> q;		// BFS queue
    queue<pair<int, int>> points;	// 인접한 그룹 좌표 queue
    visited[startX][startY] = true;
    q.push({startX, startY});
    points.push({startX, startY});
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        cnt++;
        
        for(int dir = 0;dir < 4;dir++) {
            int tempX = x + dx[dir];
            int tempY = y + dy[dir];
            
            if (tempX < 0 || tempY < 0 || tempX >= 12 || tempY >= 6)
                continue;
            
            // 방문한 적 없고 동일한 색인 경우
            if (!visited[tempX][tempY] && map[tempX][tempY] == color) {
                visited[tempX][tempY] = true;
                q.push({tempX, tempY});
                points.push({tempX, tempY});	// 인접한 그룹 좌표 queue에 넣어줌
            }
        }
    }
    
    // 인접하고 동일한 색이 4개 이상이라면
    if (cnt >= 4) {
    	// 그룹 좌표의 값을 *로 바꿔줌 (터트려야 하기 때문)
        while(!points.empty()) {
            int x = points.front().first;
            int y = points.front().second;
            points.pop();
            
            map[x][y] = '*';
        }
        return true;
    }
    
    else
        return false;
}

bool checkChain() {
    bool isChain = false;
    
    for(int i = 11;i >= 0;i--) {
        for(int j = 0;j < 6;j++) {
            if (map[i][j] != '.' && !visited[i][j]) {
                if (BFS(i, j)) {
                    isChain = true;
                }
            }
        }
    }

    return isChain;
}

// 3~4. 뿌요를 아래로 내림
void puyoDown() {
    for(int j = 0;j < 6;j++) {
        for(int i = 11;i >= 0;i--) {
            int row = i;
            
            // 이때 맨 밑의 뿌요가 터져야 한다면
            if (map[row][j] == '*') {
            	// 그 위의 행부터 값을 덮어씌워 줌
                while(row >= 1) {
                    map[row][j] = map[row - 1][j];
                    row--;
                }
                // 맨 처음 행은 . 로 초기화
                map[row][j] = '.';
                
                // 이 경우 한번 더 검사해야 하기 때문에 반복연산자 수 증가
                i++;
            }
        }
    }
}

// BFS 방문 처리 초기화
void resetVisited() {
    for(int i = 0;i < 12;i++) {
        for(int j = 0;j < 6;j++) {
            visited[i][j] = false;
        }
    }
}

int main() {
    for(int i = 0;i < 12;i++) {
        string str;
        cin>>str;
        
        for(int j = 0;j < 6;j++) {
            map[i][j] = str[j];
            visited[i][j] = false;
        }
    }
    
    int chainCount = 0;
    while(1) {
    	// 더 이상 연쇄 반응이 없다면 종료
        if (!checkChain()) {
            break;
        }
        
        // 연쇄 반응이 있다면 뿌요를 아래로 내리고, 연쇄 수 증가 후, 방문 처리 초기화
        else {
            puyoDown();
            chainCount++;
            resetVisited();
        }
    }
    
    cout<<chainCount;
    
    return 0;
}