[백준17835&파이썬] 다익스트라로 역방향 그래프 만들어 특정노드들로부터 가장 가까운 거리 구해 확정하기

# 문제

백준 17835 면접보는 승범이네 파이썬 풀이

 

17835번: 면접보는 승범이네

# 코드

import sys
from heapq import *
from collections import defaultdict

# N 도시의 수, M 도로의 수, K 면접장의 수
N, M, K = map(int, sys.stdin.readline().split())

graph =defaultdict(list)
for _ in range(M) :
  u,v,c = map(int,sys.stdin.readline().split())
  graph[v].append((u,c)) # 단방향을 거꾸로 연결시킨다.
targets = list(map(int,sys.stdin.readline().split()))

# - 문제 접근 방법-
# 그래프를 거꾸로 연결 시킨다. a -> b 였다면, b -> a와 같은 형태로
# 다익스트라를 한번만 돌리고, 이때 힙에 모든 면접장을 다 넣어준다
  # 한 정점으로부터 모든 정점까지의 경로를 구하는 것이 아니다.
  # 면접장으로부터 가장 가까운 노드만 구하면 되기 때문에, 힙에 면접장을 모두 넣어도 된다.


def dijkstra() :
  distance = [float('inf')] * (N + 1)
  heap = list()

  for target in targets :
    distance[target] = 0
    heappush(heap, (0, target))

  while len(heap) != 0 :
    cur = heappop(heap) # ( sum_weight , vertex )

    if distance[cur[1]] < cur[0] :
      continue

    for next in graph[cur[1]] : # ( vertex, weight )
      cost = distance[cur[1]] + next[1]
      if cost < distance[next[0]] :
        distance[next[0]] = cost
        heappush(heap,(cost, next[0]))
  return distance

result = dijkstra()
i = max(result[1:])
print(result.index(i))
print(i)

 

# 풀이

• 문제를 처음 보고서는 도시의 수(N)만큼 다익스트라 돌려서 면접장(K)중에서 가장 먼거 찾으면 될거 같다는 생각이 들었지만, 당연하게도 이렇게 풀면 시간초과가 날거 같았고 당연히 시간초과가 났다.
• 다익스트라의 요지는 한정점에서부터 모든 정점까지의 최단거리를 구할 수 있는 것이다. 그러나 위에서 했던 생각은 한정점이 너무 많기 때문에, 이 시작 정점을 줄이는 방법이 시간초과를 해결하는 것이라고 생각했다.

• 단방향 그래프로 주어졌기 때문에, 이걸 역으로 연결 시킨다면 면접장(K)에서 출발하여 모든 정점까지의 거리를 구할 수 있을 것이다. 이렇게 되면 시작 정점을 N개에서 K개로 줄일 수 있기 때문에 시간초과를 해결 할 수 있을 것이라 생각했지만, 여전히 시간초과가 발생했다. 당연하게도 "면접장의 수 K(1 ≤ K ≤ N)" 의 조건이 N개 일 수도 있기 때문에 최악의 경우는 K개로 줄인 것이 의미가 없기 때문이다.
• 역방향으로 설계했고, 면접장(K)에서 가장 가까울때 해당 노드의 거리만을 계산하면 된다. 결국 모든 정점까지의 거리가 아닌, 면접장에서부터 가장 가깝기만 하면 된다. 그리고 그 거리만을 알면 되기 때문에, 다익스트라를 관리하는 heap에 시작 정점으로 모든 면접장(K)를 넣고 돌린다면, 면접장에서 가장 가까운 노드의 거리가 구해진다.

def dijkstra() :
  distance = [float('inf')] * (N + 1)
  heap = list()

  for target in targets :
    distance[target] = 0
    heappush(heap, (0, target))
   
  # ... 코드 생략 ... #

• 결국 이문제를 해결하기 위해서는, 그래프를 역방향으로 생각하는 사고의 확장, 출발지점을 줄이기 위한 최적화를 해내면 된다.