[백준] 16681번 : 등산

16681번: 등산

16681번: 등산

📄 문제개요

• 주환이는 등산을 하는데 올라갈때는 높은 지점만 올라갈 수 있고, 내려올때는 낮은 지점으로만 내려올 수 있다고 한다. 집에서 출발하여 목표지점까지 갔다가, 고려대학교로 돌아올때, 주어진 가중치 계산이 있을때, 그 가중치 계산을 최대의 값을 구하여라.

🤔 문제분석

• 등산의 가치를 (얻은 성취감) - (소모한 체력) 본다면, 소모한 체력이 클 수록 등산의 가치가 작아진다.
• 따라서 최단 경로로 거리가 가장 항상 짧은 순으로 이동해야한다. 데이크스트라 알고리즘으로 접근한다.

📝 의사코드

1. 올라갈때와 내려갈때를 구분하여 구현하였다. ( 올라갈 수 있는 방향과 내려올 수 있는 방향 그래프를 초기화)
2. 집에서 올라갈 수 있는 등산로를 선택한다. ( 해당지점은 목표가 될 수 있으니 가중치를 업데이트한다)
3. 우선순위 큐를 활용하여 올라갈 수 있는 등산로를 모두 방문한다. ( (얻은 성취감) - (소모한 체력) ) 를 업데이트 해간다.
4. 소모한 체력이 작은 값으로 올라감으로 (얻은 성취감) - (소모한 체력)값을 최대값으로 갱신하면서 올라 갈 수 있다.
5. 목표로 도달할 지점으로부터 다시 고려대학교 까지 내려간다. 이때도 소모한 체력을 최소화 해야함으로, 최단거리로 방문한다. ( 가중치를 업데이트한다 )

💻 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e15)
# 주완이는 올라갈때 (얻은 성취감) - (소모한 체력)이 가장 높은 가치가 나오게 이동한다. ( 모든 경로까지 가치가 저장된다. )
# 모든 가치가 저장된 목적지로부터 다시 고려대학교까지 내려가는데 내려갈때는 거리가 가장 짧은 순으로 내려간다.

# 1. 집에서 고려대학교를 제외한 부분을 높이가 증가하는 방향으로, 꼭대기까지 방문한다. 방문할때 각각의 가중치를 각 위치에 저장한다.
# 각 위치에서부터 고려대학교로 내려와하는데 이건, 이동하기만하므로 가중치를 빼준다.
# 계산된값중에 가장 큰 값이 가장 높은 등산 경로이다.

N, M, D, E = map(int, input().split()) #지점의개수, 경로의개수, 비례 체력 소모량, 높이 비례 성취감
h = [0]+ list(map(int, input().split())) # i번째 지점의 높이를 의미
up = [[] for _ in range(N+1)] 
down = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, n = map(int, input().split())
    if h[b] > h[a]:
        up[a].append((b, n)) # 위치, 거리
        down[b].append((a, n)) # 위치, 거리
    else:
        up[b].append((a, n)) # 위치, 거리
        down[a].append((b, n)) # 위치, 거리

up_distance = [-INF for _ in range(N+1)]
queue = []

# 가장 짧은 거리를 이동해야 가치가 크다.
for new, d in up[1]:
    heapq.heappush(queue, (d, new)) # 거리, 위치
    up_distance[new] = (E*h[new] - D*d)

while queue:
    dis, target = heapq.heappop(queue)
    
    if up_distance[target] <= (E*h[target] - D*(dis)):
        for new_target, d in up[target]:
            new_distance = dis + d
            new_cost = (E*h[new_target] - D*(new_distance))
            if new_cost > up_distance[new_target]:
                up_distance[new_target] = new_cost
                heapq.heappush(queue, (new_distance, new_target))

down_distance = [-INF for _ in range(N+1)]

# 정상에 도달한 노드들
new_queue = []
for i in range(1, N+1):
    if up_distance[i] != -INF:
        heapq.heappush(new_queue, (-up_distance[i], i)) # 최대 힙으로 탐색한다.
        down_distance[i] = up_distance[i]
        
ans = -INF
while new_queue:
    dis, node = heapq.heappop(new_queue)
    if node == N:
        ans = max(ans, -dis)
    if down_distance[node] <= -dis:
        for new_node, d in down[node]:
            new_cost = -dis - d*D
            if down_distance[new_node] < new_cost:
                down_distance[new_node] = new_cost
                heapq.heappush(new_queue, (-new_cost, new_node)) # 최대 힙으로 탐색한다.
    
if ans == -INF:
    print('Impossible')
else:
    print(ans)

🎯 피드백 및 개선사항

• 주어진 문제의 조건을 잘 파악하여 우선순위 큐를 이용하여 잘 풀면 된다.
• 처음으로,,, 등수 1위를 받아보았습니다. ( 다른사람의 풀이를 보려고 들어갔더니 내가 1등? )

❓다른사람은 어떻게 풀었을까?

• 비슷한 방식으로 문제를 해결했으므로, 스킵 하겠습니다.