반응형
문제
11559번: Puyo Puyo
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
www.acmicpc.net
풀이
1. 각각의 칸을 bfs로 탐색하여 없어지는 칸들을 구합니다.
2-1. 없어지는 칸이 없다면 더 이상 연쇄가 일어나지 않는 것이므로 루프를 종료하고 combo를 출력합니다.
2-2. 없어지는 칸이 있다면 그 칸들을 .으로 바꿔줍니다.
3. 그 후 아래칸부터 접근해 해당칸이 .이고, 그 윗칸이 .이 아닐 경우 당겨줍니다. (중력 적용)
4-1. 당겨지는 칸이 있을 경우에는 3번 과정으로 돌아가 계속 해서 당겨줍니다.
4-2. 더 이상 당겨지는 칸이 없을 경우에는 다시 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
|
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
char map[12][6];
bool ispuyo[12][6];
bool visited[12][6];
bool ischanged;
bool ismovable;
int combo;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
void bfs(int sx, int sy, char color)
{
if (visited[sy][sx])
return;
int puyosize = 1;
visited[sy][sx] = true;
queue<pair<int, int>> q;
q.push(make_pair(sx, sy));
//사이즈가 4이상이면 .으로 만들어주기 위한 queue
queue<pair<int, int>> savepuyo;
savepuyo.push(make_pair(sx, sy));
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx <= 5 && ny >= 0 && ny <= 11)
{
if (!visited[ny][nx] && map[ny][nx] == color)
{
visited[ny][nx] = true;
q.push(make_pair(nx, ny));
puyosize++;
savepuyo.push(make_pair(nx, ny));
}
}
}
}
if (puyosize >= 4)
{
ischanged = true;
while (!savepuyo.empty())
{
int px = savepuyo.front().first;
int py = savepuyo.front().second;
ispuyo[py][px] = true;
savepuyo.pop();
}
}
}
int main()
{
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 6; j++)
cin >> map[i][j];
}
while (1)
{
ischanged = false;
memset(visited, 0, sizeof(visited));
memset(ispuyo, 0, sizeof(ispuyo));
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 6; j++)
{
//. 이면 방문처리, 문자면 그 문자 BFS
if (map[i][j] == '.')
{
visited[i][j] = true;
}
else
{
bfs(j, i, map[i][j]);
}
}
}
//변화 없으면 끝
if (!ischanged)
break;
combo++;
//ispuyo인것들 .으로 바꿔주기
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 6; j++)
{
if (ispuyo[i][j])
{
map[i][j] = '.';
}
}
}
//아래칸 .인 뿌요들 밑으로 밀기
while (1)
{
ismovable = false;
for (int i = 11; i >= 1; i--)
{
for (int j = 5; j >= 0; j--)
{
if (map[i][j] == '.' && map[i - 1][j] != '.')
{
map[i][j] = map[i - 1][j];
map[i - 1][j] = '.';
ismovable = true;
}
}
}
if (!ismovable)
break;
}
}
//연쇄 출력
cout << combo;
return 0;
}
|
cs |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 5430] AC (C++) (0) | 2021.08.29 |
|---|---|
| [백준 11000] 강의실 배정 (C++) (0) | 2021.08.27 |
| [백준 16236] 아기 상어 (C++) (0) | 2021.08.26 |
| [백준 15681] 트리와 쿼리 (C++) (0) | 2021.08.26 |
| [백준 2493] 탑 (C++) (0) | 2021.08.25 |