[백준 16681] 등산
1. 문제 설명
2. 문제 분석
다익스트라 알고리즘을 통해 집에서 목표까지의 최단 거리를 구하자. 학교에서 목표까지의 최단 거리 또한 구할 수 있다. 특정 목표를 경유지로 사용할 수 있다면 (즉 다익스트라로 얻어낸 거리값이 무한대가 아닐 때) 성취감과 거리값의 차 중 최댓값을 구할 수 있다.
- 다익스트라를 통해 접근하는 건 곧바로 알 수 있었는데, 경유지 최단 거리를 얻을 때 학교에서 거꾸로가 아니라 집에서 목표까지 구한 뒤, 목표에서 학교까지의 다익스트라를 돌렸기 때문에 시간 초과가 났다. 당연히 학교를 시작 노드로 한 다익스트라 알고리즘으로 얻은 거리값 리스트로 한 번에 처리할 수 있었는데, 일종의 고정 관념에 사로 잡혀 있었나.
3. 나의 풀이
import sys
import heapq
INF = sys.maxsize
n, m, d, e = map(int, sys.stdin.readline().rstrip().split())
heights = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
nodes = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, c])
nodes[b].append([a, c])
def Dijkstra(start):
distances = [INF for _ in range(n+1)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if heights[cur_node] < heights[next_node] and distances[next_node] > cur_cost + next_cost:
# 높이에 따라 이동 가능
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
dist_start = Dijkstra(1)
dist_goal = Dijkstra(n)
ans = -INF
for idx in range(2, n):
d1, d2 = dist_start[idx], dist_goal[idx]
# 집 -> idx (목표) -> 학교 이동 최소 거리
if d1 == INF or d2 == INF: continue
# INF면 이동 불가능한 목표
ans = max(ans, heights[idx]*e - (d1 + d2) * d)
if ans == -INF: print("Impossible")
else: print(ans)
Author And Source
이 문제에 관하여([백준 16681] 등산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-16681-등산
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
다익스트라 알고리즘을 통해 집에서 목표까지의 최단 거리를 구하자. 학교에서 목표까지의 최단 거리 또한 구할 수 있다. 특정 목표를 경유지로 사용할 수 있다면 (즉 다익스트라로 얻어낸 거리값이 무한대가 아닐 때) 성취감과 거리값의 차 중 최댓값을 구할 수 있다.
- 다익스트라를 통해 접근하는 건 곧바로 알 수 있었는데, 경유지 최단 거리를 얻을 때 학교에서 거꾸로가 아니라 집에서 목표까지 구한 뒤, 목표에서 학교까지의 다익스트라를 돌렸기 때문에 시간 초과가 났다. 당연히 학교를 시작 노드로 한 다익스트라 알고리즘으로 얻은 거리값 리스트로 한 번에 처리할 수 있었는데, 일종의 고정 관념에 사로 잡혀 있었나.
3. 나의 풀이
import sys
import heapq
INF = sys.maxsize
n, m, d, e = map(int, sys.stdin.readline().rstrip().split())
heights = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
nodes = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, c])
nodes[b].append([a, c])
def Dijkstra(start):
distances = [INF for _ in range(n+1)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if heights[cur_node] < heights[next_node] and distances[next_node] > cur_cost + next_cost:
# 높이에 따라 이동 가능
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
dist_start = Dijkstra(1)
dist_goal = Dijkstra(n)
ans = -INF
for idx in range(2, n):
d1, d2 = dist_start[idx], dist_goal[idx]
# 집 -> idx (목표) -> 학교 이동 최소 거리
if d1 == INF or d2 == INF: continue
# INF면 이동 불가능한 목표
ans = max(ans, heights[idx]*e - (d1 + d2) * d)
if ans == -INF: print("Impossible")
else: print(ans)
Author And Source
이 문제에 관하여([백준 16681] 등산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-16681-등산
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import heapq
INF = sys.maxsize
n, m, d, e = map(int, sys.stdin.readline().rstrip().split())
heights = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
nodes = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, c])
nodes[b].append([a, c])
def Dijkstra(start):
distances = [INF for _ in range(n+1)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if heights[cur_node] < heights[next_node] and distances[next_node] > cur_cost + next_cost:
# 높이에 따라 이동 가능
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
dist_start = Dijkstra(1)
dist_goal = Dijkstra(n)
ans = -INF
for idx in range(2, n):
d1, d2 = dist_start[idx], dist_goal[idx]
# 집 -> idx (목표) -> 학교 이동 최소 거리
if d1 == INF or d2 == INF: continue
# INF면 이동 불가능한 목표
ans = max(ans, heights[idx]*e - (d1 + d2) * d)
if ans == -INF: print("Impossible")
else: print(ans)
Author And Source
이 문제에 관하여([백준 16681] 등산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-16681-등산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)