[백준/BOJ] 백준 22944번 : 죽음의 비

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

22944번: 죽음의 비

 

시작 지점에서 도착 지점(안전지대)까지 bfs(너비 우선 탐색)을 통해 이동한다, 이때, 이동하려는 위치에 저장된 값보다 체력+우산내구도 값이 더 큰 경우가 일 때 해당 위치를 bfs의 큐에 넣는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <string>
using namespace std;

int n, h, d;
vector<string> board;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int solve(pair<int, int> start, pair<int, int> dest) {
	vector<vector<int>> discovered(500, vector<int>(500, 0)); //[x][y] = 해당 위치의 (최대 체력 + 내구도)
	queue<tuple<int, int, int, int, int>> q; //(x,y,체력,가진 우산의 내구도,깊이)

	discovered[start.first][start.second] = h;
	q.push(make_tuple(start.first, start.second, h, 0, 0));

	while (!q.empty()) {
		pair<int, int> here = make_pair(get<0>(q.front()), get<1>(q.front()));
		int here_hp = get<2>(q.front());
		int here_umbrella = get<3>(q.front());
		int here_depth = get<4>(q.front());
		q.pop();

		if (here == dest) {
			return here_depth;
		}

		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
			int there_hp = here_hp;
			int there_umbrella = here_umbrella;
			int there_depth = here_depth + 1;

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n) {
				if (board[there.first][there.second] == '.') {
					//비를 밪는다
					if (there_umbrella <= 0) {
						there_hp--;
					}
					else {
						there_umbrella--;
					}
				}

				else if (board[there.first][there.second] == 'U') { //우산의 위치일때

					there_umbrella = d; //새로운 우산을쓴다

					//비를 밪는다
					if (there_umbrella <= 0) {
						there_hp = here_hp--;
					}
					else {
						there_umbrella--;
					}
				}

				//체력이 0보다 크고, 해당 위치에서 체력+우산내구도 값이 더 큰 경우가 있으면 그 경우는 탐색한다
				//우산 위치에서 썻던 우산을 또 쓰는거 아닌지 고려하는거는, 만약 우산 위치에서 이전에 썻던 우산을 또 쓰는 경우 해당 위치에서 체력+우산내구도 값이 이전보다 더 큰 경우가 있을 수 없으므로 따로 체크하지 않는다
				if (there_hp > 0 && discovered[there.first][there.second] < there_hp + there_umbrella) {
					discovered[there.first][there.second] = there_hp + there_umbrella;
					q.push(make_tuple(there.first, there.second, there_hp, there_umbrella, there_depth));
				}


			}
		}
	}

	return -1;
}

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

	cin >> n >> h >> d;

	pair<int, int> start;
	pair<int, int> dest;
	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < n; j++) {
			if (input[j] == 'S') {
				start = make_pair(i, j);
			}

			if (input[j] == 'E') {
				dest = make_pair(i, j);
			}
		}

		board.push_back(input);
	}

	int result = solve(start, dest);

	cout << result;

	return 0;
}