백준 온라인 저지의 11559번 Puyo Puyo 문제입니다.
[링크] https://www.acmicpc.net/problem/11559
문제 조건과 설명
뿌요뿌요의 룰은 다음과 같다.
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
12 * 6 의 배열로 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산해야 한다.
Input
12*6의 문자가 주어진다.
이때 . 은 빈공간이고 . 이 아닌것은 각각의 색깔의 뿌요(R, G, P, Y)를 나타낸다.
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.(모두 대문자)
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태(즉 뿌요 아래에 빈 칸이 있는 경우는 없음) 이다.
Output
현재 주어진 상황에서 몇연쇄가 되는지 출력한다. (하나도 터지지 않는다면 0을 출력)
게임 룰 이해하기
먼저 뿌요뿌요 게임의 정확한 룰을 이해하여야 답을 구할 수 있을 것입니다.
초기에는 뿌요들 아래에 빈 칸이 없는 형태로 주어집니다.
- (상황 1) 터진 횟수 : 누적 1회
이제 이 상황에서 4개 이상 상/하/좌/우로 연결되어 터질 수 있는 것들을 탐색하고 터뜨립니다.
주의해야 할 것은, 두 그룹이 터진다고 해서 터지는 횟수를 총 2회라고 하면 안 됩니다.
이 문제는 현 상황에서 동시에 터질 수 있는 경우, 터지는 횟수를 1회로 카운트 하라고 주어졌기 때문입니다.
- (상황 2)
터져서 빈 칸이 된 곳 위에 있던 뿌요는, 아래에 있는 뿌요 바로 위에 떨어집니다.
- (상황 2) 터진 횟수 : 누적 2회
낙하된 뿌요가 밑의 뿌요들과 연결되어 또 하나의 4개 이상 모임이 되고, 이것들도 터집니다.
- (상황 3)
더 이상 터질 뿌요가 없으면 종료합니다.
생각한 아이디어
12 * 6 칸 밖에 되지 않아서, 모든 칸을 대상으로 검색해도 괜찮겠다는 생각을 했습니다.
빈 칸이 아닐 경우, 연결되어 갈 수 있을 때까지 계속 길을 찾아가야 하므로 DFS 혹은 BFS 로 풀 수 있을 것입니다.
이 때 계속 갈 수 있는 조건은 ‘다음 칸도 내 칸과 동일한 색상일 경우’ 일 것입니다.
저는 아래와 같이 과정을 나누었습니다.
- (1) 필드의 모든 칸을 탐색하면서, 그룹으로 묶여 터질 수 있는 칸들만 visit 배열에 1로 표시합니다.
- (2) 여기까지 하면 터지는 뿌요에 대한 처리가 모두 완료되므로, 터진 횟수를 1 증가시킵니다.
- (3) 1로 표시된 칸들을 모두 ‘.’ 문자로 변경합니다. ▶ 1로 표시된 칸들을 터지게 하는 상황
- (4) 필드의 칸들 중 뿌요가 있는 칸에 한해서, 자신의 밑에 있는 칸들을 차례로 살펴보고(한칸 밑, 두칸 밑, …) 가장 마지막으로 ‘.’가 있는 곳까지 내려가게 합니다.
- 자신의 밑에 있는 칸들은, 자신과 열 번호는 같고 행 번호는 더 큰 것들이 됩니다.
- 여기까지 하면 1회차 상황이 종료됩니다.
그런데 (1)번 과정을 DFS로 진행하다 보니, 위의 그림에서 (상황 2) 와 같은 모양이 왔을 때 터질 수 있는 뿌요 그룹에만 원활하게 visit 에 1을 체크하기가 어려웠습니다.
- 그림의 (상황 1) 에서 터졌던 두 그룹은 모두 한 방향으로 탐색이 가능합니다.
- 하지만 (상황 2) 에서 터진 뿌요들은 어디에서 탐색을 시작해도 방향을 최소 한 번은 반대로 바꿔야 그룹의 모든 뿌요를 탐색할 수 있습니다.
그래서 DFS 대신 BFS로 알고리즘을 변경하고 다시 짰습니다.
- BFS는 나를 기준으로 상, 하, 좌, 우 를 먼저 다 살펴보고, 갈 수 있는 것들은 미리 큐에 push해 놓은 뒤 탐색을 진행하기 때문에 제가 생각한 이러한 상황에서 용이합니다.
(단지 저는 BFS로 했을 뿐이지 DFS로도 풀 수 있는 문제입니다)
그리고 최소 4개 이상 연결되어야 터질 수 있으므로, 갈 수 있는 칸에 방문할 때마다 그 칸들의 좌표가 담긴 벡터를 만듭니다. 그러면 이것이 경로가 될 것입니다.
만약 벡터의 크기가 4보다 작으면, 그 칸들의 모든 방문을 취소해야 합니다.(visit를 0으로 변경)
즉, 뿌요가 3개 연결되어 있었으면 이들의 방문은 다시 0으로 만들어 줘야 나중에 터지지 않게 할 수 있습니다.
(1)번 과정을 구현하는 것이 관건이었던 문제 같습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int N;
string arr[12];
int visit[12][6];
bool FourCnt = false; // 4개 이상 모였는지 확인하는 변수
queue <pair<int, int>> q;
vector <pair<int, int>> v;
// 밑으로 내려갈 수 있으면, 내려가게 한다. 그 칸의 y좌표(행번호) 값을 리턴한다.
int isBottomDot(int y, int x){
int tempY = -1;
for (int i = y; i < N; i++) {
if (arr[i][x] == '.') {
tempY = i;
}
}
return tempY;
}
void bfs(int y, int x) {
q.push({ y, x }); // 현 위치 푸쉬
v.push_back({ y,x }); // 처음 방문한 칸을 푸쉬
while (!q.empty()) {
int idxY = q.front().first;
int idxX = q.front().second;
visit[idxY][idxX] = 1;
q.pop();
for (int i = 0; i < 4; i++) {
int ty = idxY + dy[i];
int tx = idxX + dx[i];
// 조건을 만족할 때에만 큐에 푸쉬한다.
if (ty < N && ty >= 0 && tx < 6 && tx >= 0
&& !visit[ty][tx] && arr[idxY][idxX] == arr[ty][tx]) {
q.push({ ty, tx }); // 갈 수 있는 칸을 푸쉬
v.push_back({ ty,tx }); // 방문할 경로를 푸쉬
visit[ty][tx] = 1;
}
}
}
}
int main() {
int crash = 0, tempY = -1;
N = 12;
cin.tie(NULL);
cout.tie(NULL);
// 12* 6 입력받기 완료
for (int i = 0; i < N; i++)
cin >> arr[i];
while (1) {
// (1) 이 2중 포문을 다 돌면, 일차적으로 동시에 터질 수 있는 곳들이 visit에 1로 표시된다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) {
if(arr[i][j]!= '.' && visit[i][j] != 1)
bfs(i, j);
if (v.size() >= 4) // 4개 이상 연결됬을 경우 true로 설정
FourCnt = true;
if (v.size() < 4) { // 4개 미만으로 연결된 경우 visit 취소
for (int i = 0; i < v.size(); i++) {
visit[v[i].first][v[i].second] = 0;
}
}
v.clear();
}
}
// (2) 동시다발 연쇄 1번을 추가한다.
if (FourCnt == true)
crash += 1;
else if (FourCnt == false)
break; // 다 검사했는데 터질 곳이 없으면 빠져나간다.
// (3) visit가 1로 표시된 곳을 모두 . 으로 만들어 준다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) {
if (visit[i][j] == 1) {
arr[i][j] = '.';
}
}
}
// (4) 밑에 . 이 있다면 . 이 없을 때까지 계속 위치를 밑으로 내린다.
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < 6; j++) {
tempY = -1;
if (arr[i][j] != '.') {
tempY = isBottomDot(i, j);
}
if (tempY != -1) {
arr[tempY][j] = arr[i][j]; // 가장 마지막 . 이 나온 곳으로 옮기고,
arr[i][j] = '.'; // 그 자리에 . 을 대입한다.
}
}
}
// 다음 탐색을 위한 초기화
FourCnt = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) {
visit[i][j] = 0;
}
}
}
cout << crash;
}