백준 16681번 등산

문제

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

문제풀이

사용한 알고리즘 : 다익스트라

(0) 생각

 임의의 지점 x 에 도달하여 얻는 성취감은 x의 높이 * E 입니다. 즉 성취감은 x마다 고정입니다.

 x까지 도달할 때 거리에 따라 피로도가 증가하므로 거리가 최소인 것이 이득입니다.

 

 모든 지점 i에대해

    1. 집에서 i까지 올라가는 최소거리

    2. i에서 고대까지 내려가는 최소거리 ( 고대에서 i까지 올라가는 최소거리 )

 를 구해줍니다.

 답은 모든 거리 i에대해 (i높이 * E) - (1,2 두 최소거리 합 * D) 중 최대값입니다.

(1) 코드 16~21

 다익스트라 구현을 위한 priority_queue 를 만들어놓습니다.

 pair< 지점, 지점까지 걸린 거리 > 를 저장하고 거리가 짧은게 위로 오도록 합니다.

(2) 코드 38~55

 집에서 각 지점에 올라가는 최소 거리를 구합니다. ( 다익스트라 )

(3) 코드 26~74

 고대에서 각 지점에 올라가는 최소 거리를 구합니다. ( 다익스트라 )

 ( 이는 각 지점에서 고대로 내려가는 최소 거리와 같습니다. )

(4) 코드 75~81

 집과 고대를 제외한 모든 지점의 등산가치 중 최대를 구합니다.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef pair<int, ll> pii; // < 노드 , 노드까지 걸린 거리 >
	const int MAX = 100005;
	const ll INF = 1987654321987654321;
	int N, M, D, E;
	ll height[MAX];
	vector<pii> adj[MAX]; // pair< 연결 노드, 연결 거리 >
	// From_house[x] : 집에서 x까지 올라가는 최소거리
	ll From_house[MAX];
	// From_Korea[x] : 고대에서 x까지 올라가는 ( x에서 고대까지 내려오는 ) 최소거리
	ll From_Korea[MAX];
	struct cmp {
	bool operator()(const pii& u, const pii& v) {
	return u.second > v.second; // 거리 짧은게 위로
	}
	};
	priority_queue<pii, vector<pii>, cmp> pq;
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> D >> E;
	for (int i = 1; i <= N; ++i) cin >> height[i];
	for (int i = 0; i < M; ++i) {
	int a, b;
	ll n;
	cin >> a >> b >> n;
	adj[a].push_back(pii(b, n));
	adj[b].push_back(pii(a, n));
	}
	// 집에서 임의의 x에 오르는 거리 + x 에서 고대까지 내려가는 거리 구할꺼다.
	// 거리가 짧은게 이득이겠다.
	// x에서 얻는 성취감 - 위의 두 거리 합에서 오는 피로도 최대를 구할꺼다.
	// 집 - > x 오르기
	fill(From_house, From_house + MAX, INF);
	From_house[1] = 0LL;
	pq.push(pii(1, 0LL));
	while (!pq.empty()) {
	int curr = pq.top().first;
	ll v = pq.top().second;
	pq.pop();
	if (v > From_house[curr]) continue; // 중복제거
	for (auto it : adj[curr]) {
	int next = it.first;
	ll dist = it.second;
	if (height[next] <= height[curr]) continue; // 올라갈꺼다
	if (v + dist < From_house[next]) { // 거리 짧게 가는게 이득 ( 피로도 낮음 )
	From_house[next] = v + dist;
	pq.push(pii(next, From_house[next]));
	}
	}
	}
	// 고대 -> x 오르기 ( x에서 고대 내려가기 )
	fill(From_Korea, From_Korea + MAX, INF);
	From_Korea[N] = 0;
	pq.push(pii(N, 0));
	while (!pq.empty()) {
	int curr = pq.top().first;
	ll v = pq.top().second;
	pq.pop();
	if (v > From_Korea[curr]) continue; // 중복제거
	for (auto it : adj[curr]) {
	int next = it.first;
	ll dist = it.second;
	if (height[next] <= height[curr]) continue; // 올라갈꺼다
	if (v + dist < From_Korea[next]) { // 거리 짧게 가는게 이득 ( 피로도 낮음 )
	From_Korea[next] = v + dist;
	pq.push(pii(next, From_Korea[next]));
	}
	}
	}
	ll ans = -INF;
	for (int i = 2; i < N; ++i) {
	if (From_house[i] == INF || From_Korea[i] == INF) continue; // 집이나 고대에서 못가면 패스
	ll succ = height[i] * E; // 성취감
	ll tired = (From_house[i] + From_Korea[i]) * D; // 소모한 체력
	ans = max(ans, succ - tired);
	}
	if (ans == -INF) cout << "Impossible" << '\n';
	else cout << ans << '\n';
	return 0;
	}

view raw BOJ 16681.cpp hosted with ❤ by GitHub