백준 20005번: 보스몬스터 전리품 (C++)

https://www.acmicpc.net/problem/20005

20005번: 보스몬스터 전리품

 

풀이

최소로 보스몬스터에 접근해야하는 거리를 알아야하기 때문에 BFS 를 사용했다.

 

전체 map 을 탐색하면서 소문자 알파벳이 있을 경우 BFS 를 돌려주었는데 

방문 체크를 하기 위해 visited 배열을 3차원으로 선언했고 

보스몬스터에 접근하게 되면 도착시간을 alpha 배열에 넣어주고 BFS 를 종료시켰다.

 

그리고 HP <= 0 일 때까지 alpha 배열을 탐색, 도착시간을 1 부터 늘려가며

해당되는 dps 를 빼주었다.

 

while 문 안에 if (HP <= 0) 문은 밖으로 빼주는 게 좋을 것 같다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int M, N, P, HP;
char board[1001][1001];
int visited[1001][1001][27] = { 0, };
int alpha[26] = { 0, };
int goY[4] = { 1,-1,0,0 }, goX[4] = { 0,0,1,-1 };
unordered_map<char, int> player;

bool is_in_board(int y, int x) {
	if (y < 0 || x < 0 || y >= M || x >= N) return false;
	return true;
}

void bfs(int y, int x, char c) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x][c] = 1;

	while (!q.empty()) {
		int nowY = q.front().first, nowX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = nowY + goY[i], nextX = nowX + goX[i];

			if (!is_in_board(nextY, nextX)) continue;
			if (board[nextY][nextX] == 'X') continue;
			if (visited[nextY][nextX][c]) continue;
			if (board[nextY][nextX] == 'B') {
				alpha[c - 'a'] = visited[nowY][nowX][c];
				return;
			}
			visited[nextY][nextX][c] = visited[nowY][nowX][c] + 1;
			q.push({ nextY, nextX });
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> M >> N >> P;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) cin >> board[i][j];
	}
	for (int i = 0; i < P; i++) {
		char c;
		int a;
		cin >> c >> a;
		player.insert({ c,a });
	}
	cin >> HP;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] >= 'a' && board[i][j] <= 'z') bfs(i, j, board[i][j]);
		}
	}
	while (HP>0) {
		for (int j = 1; j <= 1000000; j++) {
			int cnt = 0;
			for (int i = 0; i < 26; i++) {
				if (alpha[i] <= j && alpha[i] > 0) {
					HP -= player[i + 'a'];
					cnt++;
				}
			}
			if (HP <= 0) {
				cout << cnt;
				return 0;
			}
		}
	}

}