[Algorithm] 1238. 파티

1238: 파티(다익스트라)

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

• 문제 티어 : G3
• 풀이 여부 : Failed → Solved
• 소요 시간 : 00:23:01

정답 코드

import sys, heapq
input = sys.stdin.readline

N, M, X = map(int, input().rstrip().split()) # N:학생수, M:도로개수, X:마을수
arr = [[] for _ in range(N+1)] # 1~N번 마을(현재위치 -> X로 가는 방향)
rev_arr = [[] for _ in range(N+1)] # X -> 현재위치로 돌아오는 방향
for _ in range(M):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w)) # u -> v : w의 비용
  rev_arr[v].append((u, w)) # v -> u : w의 비용(역방향 경로 저장)

def dijkstra(arr, start):
  costs = [float('inf')] * (N+1)
  pq = []
  heapq.heappush(pq, (0, start)) # 우선순위큐에 넣은 순서: (cost, node)
  costs[start] = 0

  while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    if cur_cost < costs[cur_node]:
      continue
    for next_node, cost in arr[cur_node]: # 배열에 넣은 순서: (node, cost)
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]:
        heapq.heappush(pq, (next_cost, next_node))
        costs[next_node] = next_cost

  return costs

to_X = dijkstra(arr, X) # X에서 각 마을로 가는 최소비용
from_X = dijkstra(rev_arr, X) # 각 마을에서 X로 가는 최소비용

max_time = 0
for i in range(1, N+1):
  max_time = max(max_time, to_X[i] + from_X[i]) # 왕복경로로 최대값 갱신
print(max_time)

접근 방식

“집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 주어진다” → 왕복 이동이 가능한 데이터

즉, arr과 reversed_arr 로 u → v : w의 비용, v → u : w의 비용으로 이동이 가능하다는 의미이다.

for _ in range(M):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w)) # u -> v : w의 비용
  rev_arr[v].append((u, w)) # v -> u : w의 비용(역방향 경로 저장)

가중치 배열을 초기화할 때, 위와 같은 방식으로 arr과 rev_arr의 값을 지정해준다.

다익스트라의 템플릿 코드는 동일하지만, 최소비용을 계산하는 방법은 X로 가는 비용, X에서 돌아가는 비용 으로 start 값을 달리해서 2회 다익스트라 함수를 호출해야 한다.

to_X = dijkstra(arr, X) # X에서 각 마을로 가는 최소비용
from_X = dijkstra(rev_arr, X) # 각 마을에서 X로 가는 최소비용

왕복 비용의 조회가 완료되면, 1번 도시에 사는 학생부터 N번 도시에 사는 학생까지 순회하며 최대 시간이 소요된 학생을 찾는다.

→ 로직 정리 : 각 학생 별 최소비용을 들이는 방식으로 X까지 왕복 → 최소비용 중 최단비용 찾기

max_time = 0
for i in range(1, N+1):
  max_time = max(max_time, to_X[i] + from_X[i]) # 왕복경로로 최대값 갱신
print(max_time)

잘못된 접근 방식(+ 코드)

import sys, heapq
input = sys.stdin.readline

N, M, X = map(int, input().rstrip().split()) # N:학생수, M:도로개수, X:마을수
arr = [[] for _ in range(N+1)] # 1~N번 마을
for _ in range(M):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w))
ans = [0 for _ in range(N+1)] # 학생별 X까지의 비용 저장 배열

def dijkstra(arr, start, final):
  costs = [float('inf')] * (N+1)
  pq = []
  heapq.heappush(pq, (0, start)) # 우선순위큐에 넣은 순서: (cost, node)
  costs[start] = 0

  while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    if cur_cost < costs[cur_node]:
      continue
    for next_node, cost in arr[cur_node]: # 배열에 넣은 순서: (node, cost)
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]:
        heapq.heappush(pq, (next_cost, next_node))
        costs[next_node] = next_cost
  return costs[final]

for i in range(1, N+1):
  ans[i] = dijkstra(arr, i, X)

print(ans)

X까지의 비용만을 계산했음 → 문제 의미 : 현재 위치 → X → 현재위치 왕복에 소요되는 최단경로가 필요했던 문제

배운점 또는 느낀점

다익스트라로 왕복을 처리하는 문제는 처음 풀어봤다.

문제의 조건을 잘 읽어보고, 이 문제와 같이 “집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터”만 입력된다면 arr과 rev_arr을 사용해 가중치 배열을 초기화하자.