반응형
문제 링크: https://www.acmicpc.net/problem/16920
16920번: 확장 게임
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위
www.acmicpc.net
<문제 풀이> BFS 알고리즘
라운드마다 각 플레이어 별로 BFS를 돌리면 되는데, i번 플레이어의 최대 이동 횟수를 큐가 비었는지를 검사하는 while문에 같이 넣고 1씩 감소시켜주면 됩니다.
+ 최대 이동 횟수를 while문에 같이 넣어주면 플레이어의 모든 성을 최대 이동 횟수까지 움직여볼 수 있음
+ while문을 한번 돌 때 큐 안에는 플레이어의 각 성에서 움직인 거리가 같은 정점들로 구성되어 있습니다.
<C++ 소스 코드>
|
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
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0 , -1, 0};
vector<pair<int, int> > player[10];
int res[10];
int s[10];
char board[1000][1000];
int n, m, p;
void bfs() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] != '.' && board[i][j] != '#') {
player[board[i][j] - '0'].push_back({ i, j });
}
}
}
queue< pair<int, int > > Q[10];
for (int i = 1; i <= p; i++) {
for (auto castle : player[i]) {
Q[i].push({ castle.X, castle.Y });
res[i]++;
}
}
while (true) { //라운드 시작
bool success = false;
for (int i = 1; i <= p; i++) { //1번 플레이부터 시작
int s_len = s[i]; //i번 플레이어의 최대 이동 횟수
while (!Q[i].empty() && s_len--) { // i번 플레이어 BFS
int Q_size = Q[i].size();
for(int j=0; j<Q_size; j++){
auto cur = Q[i].front(); Q[i].pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
if (board[nx][ny] == '.') { // 성을 건설할 수 있으면
Q[i].push({ nx, ny });
board[nx][ny] = board[cur.X][cur.Y];
res[i]++;
success = true;
}
}
}
}
}
if (!success) break;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> p;
for (int i = 1; i <= p; i++) {
cin >> s[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
bfs();
for (int i = 1; i <= p; i++) {
cout << res[i] << ' ';
}
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 1967번] 트리의 지름 (0) | 2021.12.13 |
|---|---|
| [백준 2331번] 반복수열 (0) | 2021.12.12 |
| [백준 11967번] 불켜기 (0) | 2021.12.04 |
| [백준 3197번] 백조의 호수 (0) | 2021.12.02 |
| [백준 4963번] 섬의 개수 (0) | 2021.11.25 |