[백준 20005] 보스몬스터 전리품 (C++)

문제 링크: www.acmicpc.net/problem/20005

20005번: 보스몬스터 전리품

1. 주의할 점

- AC가 나와도 필요없는 작업은 하지 않도록 노력한다(Ex. '각 플레이어->보스까지의 거리' 대신 보스->각 플레이어까지의 거리)

- 보스가 플레이어에게 도달해도 4방향 이동은 이어서 한다

 

2. 구현

- 2가지의 방법으로 풀었다(단, BFS의 방법은 같다)

 

(0) 공통(BFS)

- 보스를 위치를 기준으로 큐에 담아서 각 플레이어까지 도달한다

 

(1) BFS + 우선순위 큐

- BFS를 통해 보스 -> 각 플레이어까지 도달하는데 걸리는 시간을 구하며, 해당 정보를 info2 구조체에 담아서 arrTime을 기준으로 오름차순으로 정렬할 우선순위큐에 넣는다

- info2 구조체의 arrTime: 보스 -> 각 플레이어까지 도달하는데 걸리는 시간

- info2 구조체의 c: 보스가 어떤 플레이어에게 도달했는지

- 모든 플레이의 정보가 우선순위큐에 저장되었다면, 주석에 설명된 변수 3개를 이용한다(cnt, ct, sum)

- 만약 우선순위 큐의 가장 상단에 위치한 플레이어가 Ct시간에 보스에 도달했다면(At), 플레이어 추가와 합 DPS를 증가시킨다. Ct보다 늦게 도착하면 안의 While문을 종료한다

- 모든 플레이어를 참가시키면서 우선순위큐가 빈 경우, 밖의 While문을 종료한다(모두 참가했기 때문)

- 다음 플레이어 도착시간까지 보스처치를 할 수 있다면 밖의 While문을 종료. 처치가 불가능할 경우, 위의 작업 반복

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int x, y, val;
};
struct info2 {
	char c;
	int arrTime;
};
struct cmp {
	bool operator()(info2 &a, info2 &b) {
		return a.arrTime > b.arrTime;
	}
};
info tmp;
info2 tmp2; 
int row, col, player, bx, by, val, hp;
char arr[1000][1000];
bool check[1000][1000] = { false, };
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int dps[26];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> player;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B') {
				bx = j;
				by = i;
				arr[i][j] = '.';
			}
		}
	for (int i = 0; i < player; i++) {
		char c;
		cin >> c >> val;
		dps[c - 'a'] = val;
	}
	cin >> hp;		//보스 체력

	//보스를 공격하는 플레이어 도착정보
	priority_queue<info2, vector<info2>, cmp> pq;
	//보스->플레이어까지의 거리
	queue<info> q;
	tmp.x = bx;
	tmp.y = by;
	tmp.val = 0;
	q.push(tmp);
	check[by][bx] = true;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cv = q.front().val;
		q.pop();
		if (arr[cy][cx] != '.') {		//플레이어 위치
			tmp2.arrTime = cv;
			tmp2.c = arr[cy][cx];
			pq.push(tmp2);
		}
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < col && ny < row && !check[ny][nx] && arr[ny][nx] != 'X') {
				check[ny][nx] = true;
				tmp.x = nx;
				tmp.y = ny;
				tmp.val = cv + 1;
				q.push(tmp);
			}
		}
	}

	int cnt = 0;	//참가한 플레이어
	int ct = pq.top().arrTime;		//현재 시간
	int sum = 0;	//참가한 플레이어들의 dps합

	while (!pq.empty()) {
		while (!pq.empty()) {
			char cc = pq.top().c;
			int at = pq.top().arrTime;
			if (at == ct) {		//같은 시간에 도착한 경우
				int cdps = dps[cc - 'a'];
				sum += cdps;
				cnt++;
				pq.pop();
			}
			else		//늦게 도착하는 경우
				break;
		}
		if (pq.empty())		//플레이어 모두 참가한 경우
			break;
		int nt = pq.top().arrTime;		//다음 플레이어 도착 시간
		if (hp <= (nt - ct)*sum) 		//다음 플레이어 도착전까지 보스처치
			break;
		else {							//처리완료 불가
			hp -= (nt - ct)*sum;
			ct = nt;
		}
	}
	cout << cnt;
	return 0;
}

 

(2) BFS + Bool[26] 배열 1개(배열대신 DPS 합으로 대체 가능)

- BFS를 수행하지만, 이전과는 다르게 매초 확인하는 작업 A를 거친다

- A는 해당 시간 이전에 보스와 플레이어가 만났다면, 해당 플레이어의 DPS만큼 수명을 깍는다 -> Player수만큼 진행. 이후, 보스의 체력이 0 이하라면 종료하며, 아니면 위의 작업을 반복한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int x, y;
};
info tmp;
int row, col, player, bx, by, val, hp;
char arr[1000][1000];
bool check[1000][1000] = { false, };
bool arrive[26] = { false, };
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int dps[26];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> player;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B') {
				bx = j;
				by = i;
			}
		}
	for (int i = 0; i < player; i++) {
		char c;
		cin >> c >> val;
		dps[c - 'a'] = val;
	}
	cin >> hp;		//보스 체력

	int cnt = 0;	//참가한 플레이어
	//보스->플레이어까지의 거리
	queue<info> q;
	tmp.x = bx;
	tmp.y = by;
	q.push(tmp);
	check[by][bx] = true;	

	while (hp>0) {
		int len = q.size();
		for (int k = 0; k < len; k++) {
			int cx = q.front().x;
			int cy = q.front().y;
			q.pop();
			if ('a'<=arr[cy][cx] && arr[cy][cx] <= 'z') {		//플레이어 위치
				arrive[arr[cy][cx] - 'a'] = true;
				cnt++;
			}
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < col && ny < row && !check[ny][nx] && arr[ny][nx] != 'X') {
					check[ny][nx] = true;
					tmp.x = nx;
					tmp.y = ny;
					q.push(tmp);
				}
			}
		}
		for (int i = 0; i < player; i++) 
			if (arrive[i]) hp -= dps[i];	
	}
	cout << cnt;
	return 0;
}