백준 11559번 Puyo Puyo 문제풀이(C++)

YooHeeJoon·2022년 10월 5일
0

백준 문제풀이

목록 보기
24/56

백준 11559번 Puyo Puyo

아이디어

뿌요뿌요의 룰은 다음과 같다.

  • 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

  • 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
  • 중력 구현

    void gravity() {
    	for (int i = 0; i < 6; i++) {
    		int idx = 11;
    		while (idx--) {
    			if (puyoPuyo[idx][i] != '.') {
    				int tmp = idx + 1;
    				if (puyoPuyo[tmp][i] == '.') {
    					while (tmp <= 11 && puyoPuyo[tmp][i] == '.') {
    						tmp++;
    					}
    					puyoPuyo[tmp - 1][i] = puyoPuyo[idx][i];
    					puyoPuyo[idx][i] = '.';
    				}
    			}
    		}
    	}
    	return;
    }



  • 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.

  • 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

  • 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
  • 터트리는지 확인

    bool isBoom() {
    	memset(visited, 0, sizeof(visited));
    	bool flag = false;
    	for (int i = 0; i < 12; i++) {
    		for (int j = 0; j < 6; j++) {
    			if (puyoPuyo[i][j] != '.' && !visited[i][j]) {
    				check(i, j);
    				if (cnt >= 4) {
    					boom(i, j, puyoPuyo[i][j]);
    					flag = true;
    				}
    				cnt = 1;
    			}
    		}
    	}
    	return flag;
    }

    4개 이상 모였는지 dfs로 확인

    void check(int y, int x) {
    	visited[y][x] = true;
    	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 || visited[ny][nx] || 
           		 puyoPuyo[y][x] != puyoPuyo[ny][nx] || puyoPuyo[ny][nx] == '.') continue;
    		visited[ny][nx] = true;
    		check(ny, nx);
    		cnt++;
    	}
    	return;
    }

    4개 이상 모이면 bfs로 터트린다

    void boom(int y, int x, char shape) {
    	queue<pair<int, int>> q;
    	q.push({ y, x });
    	while (!q.empty()) {
    		int y = q.front().first;
    		int x = q.front().second;
    		q.pop();
    		puyoPuyo[y][x] = '.';
    		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 || puyoPuyo[ny][nx] != shape) continue;
    			q.push({ ny, nx });
    		}
    	}
    	return;
    }

    문제풀이

    #include<bits/stdc++.h>
    using namespace std;
    #define MAX 8
    #define INF 2147483647
    int boomCnt = 0, cnt = 1;
    char puyoPuyo[MAX + MAX][MAX];
    bool visited[MAX + MAX][MAX];
    int dy[] = { 1,0,-1,0 };
    int dx[] = { 0,1,0,-1 };
    void check(int y, int x) {
    	visited[y][x] = true;
    	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 || visited[ny][nx] || 
           		 puyoPuyo[y][x] != puyoPuyo[ny][nx] || puyoPuyo[ny][nx] == '.') continue;
    		visited[ny][nx] = true;
    		check(ny, nx);
    		cnt++;
    	}
    	return;
    }
    void boom(int y, int x, char shape) {
    	queue<pair<int, int>> q;
    	q.push({ y, x });
    	while (!q.empty()) {
    		int y = q.front().first;
    		int x = q.front().second;
    		q.pop();
    		puyoPuyo[y][x] = '.';
    		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 || puyoPuyo[ny][nx] != shape) continue;
    			q.push({ ny, nx });
    		}
    	}
    	return;
    }
    bool isBoom() {
    	memset(visited, 0, sizeof(visited));
    	bool flag = false;
    	for (int i = 0; i < 12; i++) {
    		for (int j = 0; j < 6; j++) {
    			if (puyoPuyo[i][j] != '.' && !visited[i][j]) {
    				check(i, j);
    				if (cnt >= 4) {
    					boom(i, j, puyoPuyo[i][j]);
    					flag = true;
    				}
    				cnt = 1;
    			}
    		}
    	}
    	return flag;
    }
    void gravity() {
    	for (int i = 0; i < 6; i++) {
    		int idx = 11;
    		while (idx--) {
    			if (puyoPuyo[idx][i] != '.') {
    				int tmp = idx + 1;
    				if (puyoPuyo[tmp][i] == '.') {
    					while (tmp <= 11 && puyoPuyo[tmp][i] == '.') {
    						tmp++;
    					}
    					puyoPuyo[tmp - 1][i] = puyoPuyo[idx][i];
    					puyoPuyo[idx][i] = '.';
    				}
    			}
    		}
    	}
    	return;
    }
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	for (int i = 0; i < 12; i++) {
    		for (int j = 0; j < 6; j++) {
    			cin >> puyoPuyo[i][j];
    		}
    	}
    	int a = 6;
    	while (isBoom()) {
    		gravity();
    		boomCnt++;
    	}
    	cout << boomCnt << '\n';
    	return 0;
    }

    0개의 댓글