[C++] 백준 1486 : 등산

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

1486번: 등산

백준 1486번 등산 문제를 풀었다.

 

특정 노드에서 특정 노드까지의 최단 거리를 구하고, 간선의 가중치가 양수여서 다익스트라를 사용했다.

이 문제의 경우 가장 높은 산을 갔다가 다시 호텔로 돌아와야 하므로

호텔 -> 산 -> 호텔

이런 식으로 하나의 산에 대해 다익스트라를 두 번 실행하면 된다.

실제로는 호텔 -> 산 다익스트라는 한 번 실행하면 모두 구할 수 있고, 산 -> 호텔 다익스트라를 산의 개수만큼 실행해야 한다.

 

내가 사용한 배열은 아래와 같다

dist[x][y] : (x, y) 좌표의 산까지 가는 최단 비용을 저장

dist_back[x][y] : (x, y) 좌표에서 호텔까지 가는 최단 비용을 (0, 0)에 저장

m_pq : 산들의 좌표를 높이 순으로 정렬한 우선순위 큐

 

입력받을 때 m_pq에 산의 좌표와 높이를 넣어줬다.

 

(0, 0)에서 다익스트라를 한 번 실행해서 dist 배열을 채운다.

while 문 안에서 m_pq의 top에 있는 산을 뽑는다. 큐에 있는 산들 중 가장 높은 산의 좌표(x, y)와 높이를 알 수 있다.

해당 좌표로 다익스트라를 실행해서 dist_back 배열을 채운다.

dist[x][y] + dist_back[0][0] 의 값이 d보다 작거나 같으면, (x, y)의 산이 d 시간 이내에 갔다 올 수 있는 가장 높은 산이라는 뜻이다. 따라서 해당 산의 높이를 출력하면 정답이 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000
#define LLINF 9223372036854775800

struct Node {
	int x;
	int y;
	int cost;
	bool operator<(const Node& d) const {
		return cost > d.cost;
	}
};

struct Mountain {
	int x;
	int y;
	int height;
	bool operator < (const Mountain& m) const {
		return height < m.height;
	}
};

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
int n, m, t, d;
int map[25][25];
priority_queue<Mountain> m_pq;

void Dijkstra(int start_x, int start_y, int (*dist)[25]) {
	priority_queue<Node> pq;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = INF;
		}
	}
	dist[start_x][start_y] = 0;
	pq.push({ start_x,start_y,dist[start_x][start_y] });
	while (!pq.empty()) {
		Node temp = pq.top();
		int x = temp.x;
		int y = temp.y;
		int cost = temp.cost;
		pq.pop();

		if (cost >= d)
			continue;

		if (dist[x][y] < cost)
			continue;

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int next_cost = cost;

			if (nx < 0 || ny < 0 || nx >= n || ny >= m)
				continue;

			int diff = abs(map[nx][ny] - map[x][y]);
			if (diff <= t) {
				if (map[nx][ny] <= map[x][y]) {
					next_cost++;
					if (dist[nx][ny] > next_cost) {
						dist[nx][ny] = next_cost;
						pq.push({ nx,ny,next_cost });
					}
				}
				else {
					next_cost += diff * diff;
					if (dist[nx][ny] > next_cost) {
						dist[nx][ny] = next_cost;
						pq.push({ nx,ny,next_cost });
					}
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> t >> d;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] < 95) {
				map[i][j] = int(s[j]) - 65;
			}
			else {
				map[i][j] = int(s[j]) - 71;
			}
			m_pq.push({ i,j,map[i][j] });
		}
	}

	int dist[25][25];
	int dist_back[25][25];

	Dijkstra(0, 0, dist);

	while (!m_pq.empty()) {
		Mountain temp = m_pq.top();
		int x = temp.x;
		int y = temp.y;
		int height = temp.height;
		m_pq.pop();
		Dijkstra(x, y, dist_back);

		if (dist_back[0][0] + dist[x][y] <= d) {
			cout << height;
			break;
		}
	}

	return 0;
}