항해 99 알고리즘 TIL : 16118 달빛 여우

🚀 문제

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

🚀 정답 코드

import heapq
import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

# 인접 리스트로 그래프 정보 관리
graph = [ [] for _ in range(N + 1) ]

for i in range(1, N + 1):
  graph[i] = []

for _ in range(M):
  n1, n2, v = map(int, input().split())
  v *= 2
  graph[n1].append((n2, v))
  graph[n2].append((n1, v))

# 여우 이동 결과 계산
# 각 노드의 이동 속도 초기화
fox = [ float('inf') ] * (N + 1)
fox[1] = 0

hq = [(0, 1)]

# 가중치를 활용해서 최단 거리 계산 (다익스트라)
while hq:
  dist, cur = heapq.heappop(hq)

  if dist > fox[cur]:
    continue

  for to, cost in graph[cur]:
    new_dist = dist + cost
    if new_dist < fox[to]:
      fox[to] = new_dist
      heapq.heappush(hq, (new_dist, to))

# 늑대 이동 결과 계산
# 각 노드에 느릴 때, 빠를 때 도착하는 순간이 다르기 때문에 이차원 배열로 관리
wolf = [ [float('inf')] * 2 for _ in range(N + 1) ]
wolf[1][0] = 0

# 가중치를 통해 최단 거리 계산(다익스트라)
hq = [(0, 1, True)]

while hq:
  dist, cur, is_fast = heapq.heappop(hq)

  if is_fast and dist > wolf[cur][0]: continue
  if not is_fast and dist > wolf[cur][1]: continue
	
	# 순서(느릴때, 빠를 때)에 따라 구분해서 연산 수행
  for to, cost in graph[cur]:
    if is_fast:
      next_cost = cost // 2 + wolf[cur][0]
      if next_cost < wolf[to][1]:
        wolf[to][1] = next_cost
        heapq.heappush(hq, (next_cost, to, False))

    else :
      next_cost = cost * 2 + wolf[cur][1]
      if next_cost < wolf[to][0]:
        wolf[to][0] = next_cost
        heapq.heappush(hq, (next_cost, to, True))

answer = 0
for i in range(2, N + 1):
    if fox[i] < min(wolf[i]):
        answer += 1
print(answer)

🚀 시행착오 했던 부분

• BFS + 최단 누적 거리를 계산했다.

  → 최단 거리인 경우에는 가중치가 주어지고 그 경우에는 heap을 통해 큐를 정렬하며 최소 가중치를 먼저 계산하는 것이 바람직하다.
  

• 늑대 연산시 1차원 배열을 활용

  → 해당 노드에 빠를 때 오는지, 느릴때 오는지 순서에 따라 가중치가 변하기 때문에 시점에 따라 계산이 필요하다. 따라서 2차원 배열을 사용하는 것이 바람직하다.
  

• Heap 정렬 시에 첫번째 입력값을 우선으로 하여 정렬하기 때문에 정렬이 필요한 값을 첫번째 놓는다.

  → 이번에는 cost을 첫번째 인자로 두는 것이 연산속도가 더 빠르다.
  

• 비용 정보를 관리할 때 객체를 사용했었다.

  → 객체보다 인접 리스트를 활용하는 것이 메모리 측면에서 효율적이고, 인접 리스트도 2차원 배열 보다 튜플로 관리하는 것이 더 효율적이다.
  

• heapq 내부에서 배열보다, tuple을 사용하는 것이 더 빠르다.

  → GPT 피셜… heapq 내부에서 tuple을 사용하는 것이 더 빠르다…