[백준/BOJ] 백준 1486번 : 등산

www.acmicpc.net/problem/1486

1486번: 등산

다익스트라를 이용해 문제를 해결했다. 각각의 산에서 호텔로 가는 최단 시간을 구해서 저장해 놓고,  호텔 위치에서 각각 산으로 가는 최단 시간을 구한 뒤 d 이하 시간에 호텔로 돌아올 수 있는지 판단하였다.

 

코드

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

int n, m, t, d;
vector<vector<int>> board(25, vector<int>(25, 0));
vector<vector<int>> mountain_to_hotel(25, vector<int>(25, 0)); //산에서 호텔로 가는 최단 경로를 구한다
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int result = -1;

void Solve(pair<int, int> start)
{
	vector<vector<int>> short_time(n, vector<int>(m, 987654321));
	priority_queue<pair<int, pair<int, int>>> pq;

	short_time[start.first][start.second] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		pair<int, int> here = pq.top().second;
		int here_time = -pq.top().first;
		int here_height = board[here.first][here.second];
		pq.pop();

		if (here_time > short_time[here.first][here.second])
			continue;

		//더 높은 산에 올랐을때
		if (result < here_height)
		{
			//이곳에서 호텔로 시간안에 돌아갈 수 있는지 확인
			if (here_time + mountain_to_hotel[here.first][here.second] <= d)
				result = here_height;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			int there_height;
			int there_time;

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m)
			{
				there_height = board[there.first][there.second];

				if (abs(here_height - there_height) > t)
					continue;

				if (here_height >= there_height) //낮거나 같은곳 이동할때
				{
					there_time = here_time + 1;
				}

				else //높은곳 이동할때
				{
					there_time = here_time + pow(there_height - here_height, 2);
				}

				if (there_time <= d && short_time[there.first][there.second] > there_time)
				{
					short_time[there.first][there.second] = there_time;
					pq.push(make_pair(-there_time, there));
				}
			}
		}
	}
}

int Make_mountain_to_hotel(pair<int, int> start)
{
	vector<vector<int>> short_time(n, vector<int>(m, 987654321));
	priority_queue<pair<int, pair<int, int>>> pq;

	short_time[start.first][start.second] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		pair<int, int> here = pq.top().second;
		int here_time = -pq.top().first;
		int here_height = board[here.first][here.second];
		pq.pop();

		if (here_time > short_time[here.first][here.second])
			continue;

		//호텔 위치일때
		if (here.first == 0 && here.second == 0)
			return here_time;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			int there_height;
			int there_time;

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m)
			{
				there_height = board[there.first][there.second];

				//높이 차이가 t보다 클때
				if (abs(here_height - there_height) > t)
					continue;

				if (here_height >= there_height) //낮거나 같은곳 이동할때
				{
					there_time = here_time + 1;
				}

				else //높은곳 이동할때
				{
					there_time = here_time + pow(there_height - here_height, 2);
				}

				if (there_time <= d && short_time[there.first][there.second] > there_time)
				{
					short_time[there.first][there.second] = there_time;
					pq.push(make_pair(-there_time, there));
				}
			}
		}
	}

	//호텔로 도달 할 수 없을때
	return 987654321;
}

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

	cin >> n >> m >> t >> d;

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

		for (int j = 0; j < m; j++)
		{
			if (input[j] >= 'A' && input[j] <= 'Z')
				board[i][j] = input[j] - 'A';

			else
				board[i][j] = input[j] - 'a' + 26;
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			mountain_to_hotel[i][j] = Make_mountain_to_hotel(make_pair(i, j)); //해당 위치에서 호텔로 가는 최단시간을 구한다

	Solve(make_pair(0, 0));

	cout << result;

	return 0;
}