안녕하세요! 오늘은 BOJ 11559 - Puyo Puyo 문제를 풀어볼게요.
뿌요뿌요라는 게임에 대해서 알고 계신가요?
떨어지는 (슬라임처럼 생긴) 뿌요들을 쌓아서, 같은 색깔의 뿌요를 4개 쌓으면 '연쇄'가 일어나 뿌요들이 사라지고 상대방을 공격하는 대전 게임이에요.
실제 게임에서는 위에서 랜덤 하게 뿌요가 떨어지고, 상대방을 방해하는 요소도 있는 걸로 알고 있는데요.
이 문제는 그런 것은 배제하기로 하고, 주어진 상황에서 얼마나 연쇄가 일어나는지에 대해서 구해야 하는 문제예요.
접근 - (1) 규칙 파악
우선 문제에서 준 뿌요뿌요의 룰 5가지를 한 가지씩 차근차근 살펴볼게요.
첫 번째로, 뿌요는 중력의 영향을 받아서 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어져요.
그림과 같이 뿌요 아래에 빈 공간이 있을 경우에 중력이 작용한다고 이해하면 되겠네요.
두 번째로, 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우 연결되어 있을 시에, 연결된 같은 색 뿌요가 모두 없어지고, 1연쇄가 시작된다고 하네요.
상하좌우로 연결만 되어 있으면 되니, 위 그림과 같이 다양한 상황이 연출될 수 있겠죠?
세 번째로, 뿌요들이 없어지고 나서 위에 다른 뿌요가 있으면, 중력에 의해 아래로 떨어진다고 해요.
첫 번째 규칙에서 뿌요에게 중력이 작용한다고 했으니, 당연한 규칙이기도 해요.
네 번째로, 아래로 떨어지고 나서 다시 같은 색의 뿌요가 4개 이상 모이게 되면 다시 뿌요가 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다고 해요.
즉 그림에서 왼쪽처럼 파란색 뿌요가 4개 연결되어 있으니 1연쇄로 터지고 나면, 노란색 뿌요 두 개가 중력이 작용해서 아래로 내려오겠죠?
그러면 노란색 뿌요가 다시 4개 연결되게 되어서 터지게 될 때는 2연쇄가 되는 거예요.
마지막으로, 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고, 여러 그룹이 터지더라도 한 번의 연쇄만 추가된다고 해요.
즉, 그림에서 왼쪽처럼 파란색 뿌요가 4개 연결되어 있으니 1연쇄로 터지게 되면, 위쪽 보라색 뿌요 두 개와 노란색 뿌요 두 개가 중력이 작용하여 오른쪽 그림처럼 아래로 내려가게 돼요.
그럼 보라색 뿌요 4개와 노란색 뿌요 4개가 동시에 터지게 되고, 두 그룹이 동시에 터진 것이므로 2연쇄가 되는 거예요.
접근 - (2) 구현 방향성 잡기
이제 구현에 대해 생각해 볼게요.
초기값은 (12줄) * (6개의 문자)의 형태로 주어지는데, 입력 형태를 보면 각각의 줄에 공백이 없으므로 문자열 배열로 받는 것이 좋아 보여요.
먼저 모든 뿌요에 대하여, 뿌요 아래가 빈칸('.') 일 경우에는 중력에 의하여 위치를 바꿔주어야 해요.
중력이 작용한 후에는 모든 뿌요에 대하여, BFS를 이용해서 같은 색 뿌요가 4개 이상 연결되어 있는지 확인하고, 뿌요를 빈칸('.')으로 바꿔줘요.
가능한 모든 뿌요의 연쇄가 이루어지고 나서 만약 연쇄가 발생했다면, 연쇄 횟수를 1 증가시키고 위의 과정을 반복해요.
(터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하기 때문에, 모든 뿌요의 연쇄가 이루어지고 나서 한 번 이상 연쇄가 발생하였다면, 연쇄 횟수를 1 증가시켜요.)
만약 연쇄가 일어나지 않았다면, 반복문을 탈출해서 연쇄 횟수를 출력해 주면 될 것 같아요.
조금 더 감을 잡기 위해서 예제 입력을 따라가 볼게요.
원래는 위쪽에 더 많이 빈 공간이 있지만 생략하고 상황을 그려두었어요.
우선, 중력에 의하여 아래로 떨어질 뿌요는 없어요. (문제 조건에 의하여, 처음 주어지는 필드는 뿌요 아래에 빈칸이 있는 경우는 없어요.)
다음으로, 모든 뿌요에 대해서 BFS를 진행한다고 가정해 볼게요.
우선 색깔을 저장해 두고, 상하좌우 인접한 칸에 같은 색 뿌요가 존재하는지 확인하면 될 거예요.
그리고 같은 색 뿌요가 있다면, 그 좌표를 벡터에 담아두면 좋을 것 같아요.
BFS가 끝나고 벡터의 크기가 4 이상이라면, 같은 색 뿌요 4개 이상이 인접해 있으므로 연쇄가 일어나겠네요.
그러면 연쇄가 일어났다고 연쇄 발생 여부를 저장하는 변수를 true로 바꿔주고, 연쇄가 일어난 뿌요들을 전부 빈칸('.')으로 바꿔주어야 해요. 이래서 아까 좌표를 벡터에 담아두었어요.
이 경우 빨간색 뿌요 4개만 연쇄가 일어나겠네요.
연쇄 발생 변수가 true이니까, 연쇄 횟수를 1 증가시키고, BFS에서 사용한 visited 배열은 모두 false로 초기화해 줘요.
빨간색 뿌요가 연쇄되고 나서 다음 상황을 볼게요.
연쇄 발생 여부를 저장하는 변수를 false로 바꿔서, 이번에도 연쇄가 발생했는지 체크할 거예요.
이제 중력에 의하여 노란색 뿌요 두 개가 떨어져야 해요.
이때, 아래에 위치한 뿌요부터 중력에 의하여 떨어져야, 위의 뿌요도 정상적으로 떨어질 수 있어요.
그러므로 아랫줄부터 for문을 돌면서 뿌요 아래가 빈칸일 경우, 다른 뿌요를 만나거나 바닥을 만날 때까지 swap 해주면 중력에 의하여 뿌요가 떨어지는 것을 구현할 수 있겠네요.
그러면 아래 그림과 같이 노란색 뿌요가 떨어지게 될 거예요.
이렇게 중력에 의해서 모든 뿌요를 떨어뜨린 후에, 모든 뿌요에 대해 아까 전과 같이 BFS를 진행해요.
이번에는 노란색 뿌요 4개가 연쇄를 일으키겠네요.
그러면 연쇄 발생 여부를 저장하는 변수를 true로 바꿔주고, 연쇄가 일어난 뿌요들을 전부 빈칸('.')으로 바꿔주어야 해요.
연쇄 발생 변수가 true이니까, 연쇄 횟수를 1 증가시키고, BFS에서 사용한 visited 배열은 모두 false로 초기화해 줘요.
노란색 뿌요가 연쇄되고 나서 다음 상황을 볼 텐데, 이제 제가 어떻게 이야기할지 어느 정도 감이 오실 거예요.
연쇄 발생 여부를 저장하는 변수를 false로 바꿔서, 이번에도 연쇄가 발생했는지 체크할 거예요.
이제 중력에 의하여 초록색 뿌요 한 개가 떨어져야 해요.
초록색 뿌요 아래가 빈칸이므로, 바닥을 만날 때까지 swap 하여 뿌요를 아래로 이동시킬 거예요.
그러면 아래 그림과 같이 초록색 뿌요가 떨어지게 될 거예요.
이렇게 중력에 의해서 모든 뿌요를 떨어뜨린 후에, 모든 뿌요에 대해 아까 전과 같이 BFS를 진행해요.
이번에는 초록색 뿌요 4개가 연쇄를 일으키겠네요.
그러면 연쇄 발생 여부를 저장하는 변수를 true로 바꿔주고, 연쇄가 일어난 뿌요들을 전부 빈칸('.')으로 바꿔주어야 해요.
연쇄 발생 변수가 true이니까, 연쇄 횟수를 1 증가시키고, BFS에서 사용한 visited 배열은 모두 false로 초기화해 줘요.
자, 이제 마지막이에요!
연쇄 발생 여부를 저장하는 변수를 false로 바꿔서, 이번에도 연쇄가 발생했는지 체크할 거예요.
그런데 뿌요가 하나도 없으니, 중력에 의하여 아래로 떨어질 뿌요도 없고, BFS 할 뿌요도 없어요.
따라서 연쇄가 일어나지 않으므로 연쇄 발생 여부를 저장하는 변수가 여전히 false일 것이니, 반복문을 탈출하고 연쇄 횟수 3회를 출력하면 되겠네요.
구현
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define X first
#define Y second
using namespace std;
string field[12];
int visited[12][6];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool ispuyo = false;
void Puyo(int i, int j) {
char color = field[i][j]; // 뿌요 색깔을 저장
vector<pair<int, int>> v; // 4개 이상 뿌요가 쌓일 경우 연쇄하기 위해 뿌요의 위치를 저장할 벡터
queue<pair<int, int>> Q;
visited[i][j] = true;
Q.push({i, j}); // 초기 위치 설정
v.push_back({i, j}); // 처음 뿌요 기본값으로 벡터에 담기
while (!Q.empty()) { // BFS
pair<int, int> cur = Q.front();
Q.pop();
for (int mov = 0; mov < 4; mov++) { // 상하좌우 같은 색의 뿌요가 있는 지 확인!
int nx = cur.X + dx[mov];
int ny = cur.Y + dy[mov];
if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue; // 필드 범위를 벗어날 경우 skip
if (visited[nx][ny] || field[nx][ny] != color) continue; // 이미 방문했거나 뿌요 색이 다른 경우 skip
visited[nx][ny] = true; // 방문했다고 표시
Q.push({nx, ny}); // 다음 상하좌우 뿌요가 더 있는 지 찾기 위해 큐에 담기
v.push_back({nx, ny}); // 같은 색 뿌요의 위치를 벡터에 쌓아주기
}
}
if (v.size() >= 4) { // 4개 이상 뿌요가 모여 '연쇄'될 경우
ispuyo = true; // 연쇄됐음을 표시
for (pair<int, int> a : v) {
field[a.X][a.Y] = '.'; // 뿌요를 빈 칸으로 만들기
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 12; i++) {
cin >> field[i];
}
int result = 0; // 연쇄 횟수를 저장할 변수
do {
ispuyo = false; // 연쇄가 일어났는 지 여부를 확인할 변수
for (int i = 10; i >= 0; i--) {
// 뿌요 아래가 빈 칸일 경우 위치 변경 (마지막 줄은 변경할 필요 없음!)
// 이때, 아래에서부터 중력을 작용시켜야 정상적으로 위쪽 뿌요들까지 떨어뜨릴 수 있음.
for (int j = 0; j < 6; j++) {
int tmp = i;
while (field[tmp][j] != '.' && field[tmp+1][j] == '.') {
// 아래가 빈 칸일 경우 다른 뿌요가 나오거나 바닥이 나올 때까지 계속해서 중력에 의하여 떨어지므로 swap
swap(field[tmp][j], field[tmp+1][j]);
tmp++;
if (tmp >= 11) break; // 바닥을 만났으므로 종료
}
}
}
for (int i = 0; i < 12; i++) {
// 같은 색 뿌요가 4개 이상 연결되어 있는 지 확인하고 빈칸으로 바꾸기
for (int j = 0; j < 6; j++) {
if (!visited[i][j] && field[i][j] != '.') {
// 방문하지 않았고 뿌요라면 BFS
Puyo(i, j);
}
}
}
if (ispuyo) result++; // 연쇄됐을 경우 연쇄 횟수 증가
for (int i = 0; i < 12; i++) { // 방문 배열 초기화
for (int j = 0; j < 6; j++) {
if (visited[i][j]) visited[i][j] = false;
}
}
} while (ispuyo); // 연쇄됐을 경우 반복
cout << result;
return 0;
}
구현에 있어서 주의할 부분 몇 가지만 정리해 볼게요.
ispuyo 변수가 앞서 설명했던 연쇄가 발생하였는지 여부를 확인하는 전역변수로, 매번 반복할 때마다 false로 시작해요. (Puyo 함수에서 만약 연쇄가 발생했다면 true로 바꿔줄 거예요.)
뿌요 아래가 빈칸임을 확인하는 부분에서, 마지막 줄, 즉, 바닥일 경우에는 마지막 줄보다 아래 줄을 확인할 수가 없다는 점을 구현할 때 주의해야 해요.
또, 한 번만 아래로 내리는 것이 아니라 바닥이나 뿌요가 나올 때까지 아래 칸으로 이동시켜야 하니 while 반복문을 이용했어요.
Puyo 함수에서는 BFS를 진행하는데, 처음 위치도 visited 변수를 true로 바꾸는 것 잊지 말아 주세요. (제가 이걸로 예제 출력이 안 나와서 고생했네요 ㅠㅠ)
한번 연쇄가 끝난 후에 visited 배열을 초기화하는 것도 꼭 잊지 않아야 하겠죠?
마냥 쉽지 않은 시뮬레이션 문제였어요.
최대한 스텝 바이 스텝으로 설명드리려 노력했는데 도움이 될 수 있었으면 좋겠습니다!
'PS - Baekjoon > Simulation' 카테고리의 다른 글
| [백준, BOJ] 13335 - 트럭 (C++) (0) | 2025.02.06 |
|---|