문제 URL : https://www.acmicpc.net/problem/20005
20005번: 보스몬스터 전리품
입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입
www.acmicpc.net
문제 접근법 : 시뮬+bfs 문제입니다.
매초마다 플레이어가 동시에 움직이는데 보스에 다가가면 매초마다 보스가 맞습니다.
즉 죽을때까지 몇명의 플레이어가 보스한테까지 왔는지 확인하는 문제인데
저같은경우는 각플레이어의 위치에서 bfs를 돌려 보스한테까지 간경우를 bfs로 돌렸습니다. 그리고
해당플레이어가 보스에게 도착한경우 그플레이어는 더이상 bfs를 돌필요가 없겠지요
그리고 모두가 보스에게 다가왔따면 보스가 죽지않았을때는 어차피 언젠가는 죽게될테니
더이상 bfs를 돌리지 않아도 됩니다.
소스코드 :
|
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<bits/stdc++.h>
using namespace std;
int n, m,p;
int board[1000][1000];
char check[26][1000][1000];//최대 26명의 플레이어
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int fy, fx;
vector<pair<int, int>>pv;
int bhp, dps[26];
vector<int> v;
void input() {
cin >> n >> m >> p;
char c;
pv = vector<pair<int, int>>(p);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
if ('X' == c)
board[i][j] = 1;//벽
else if ('B' == c) {
fy = i, fx = j;//보스좌표
}
else if ('a' <= c && c <= 'z') { //플레이어의 시작좌표
pv[c - 'a'].first = i;
pv[c - 'a'].second = j;
}
}
}
for (int i = 0; i < p; i++) {
int h;
cin >> c >> h;
dps[c - 'a'] = h;//플레이어 공격력
v.push_back(c - 'a');
}
cin >> bhp; //보스체력
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
void solve() {
queue<tuple<int, int, int>> q;
for (int i = 0; i < p; i++) {
int color = v[i];
q.push({ pv[color].first,pv[color].second,color });
check[color][pv[color].first][pv[color].second] = 1;
}
int res = 0;
bool isfinish[26] = { 0 };
int damage = 0;
while (!q.empty()&&bhp>0) {
int qsize = q.size();
while (qsize--) {
int y, x, color;
tie(y, x, color) = q.front();
q.pop();
if (isfinish[color])continue;//해당플레이어가 보스에게 도착했다면 그플레이어는 돌필요가없음
if (y == fy && x == fx) {//보스도착
isfinish[color] = 1;
res++;
damage += dps[color]; //매초마다의 데미지를 증가시킴
continue;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && check[color][ny][nx] == 0&&board[ny][nx]==0) {
check[color][ny][nx] = 1;
q.push({ ny,nx,color });
}
}
}
bhp -= damage;//매초마다 데미지 가격
if (res == p)break;//전체플레이어가 보스에게 도착했다면 보스체력이 남아있다해도 언젠가 죽기때문에 bfs를 돌필요없음
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 2688 줄어들지 않아 (0) | 2022.04.07 |
|---|---|
| 백준 1103 게임 (0) | 2022.04.07 |
| 백준 9328 열쇠 (0) | 2022.03.29 |
| 백준 17140 이차원 배열과 연산 (0) | 2022.03.29 |
| 백준 2638 치즈 (0) | 2022.03.29 |
