2023/8/4

18352번: 특정 거리의 도시 찾기

import sys
import heapq

input = sys.stdin.readline

INF = int(1e9)

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

graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)

for _ in range(M):
  A, B = map(int, input().split())
  graph[A].append((B,1))      # 노드 A에서 B로가는 비용이 1이다

def dijkstra(start):
  global distance
  global graph       # 아니 이거 두개 안해줘도 되는건가?
  
  q = []
  
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q: # 등호 상관 없나..
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue

    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q,(cost,i[0]))

dijkstra(X)

cnt = 0

for i in range(1,N+1):
  if distance[i] == K:
    print(i)
    cnt += 1

if cnt == 0:
  print(-1)

노드의개수가 300,000 이고 간선의 개수가 1,000,000 이었기 때문에

개선된 다익스트라 알고리즘을 사용 해야겠다고 판단했다.

개선된 다익스트라로 모든 최단 거리를 구한다음 문제 조건에서 제시하는 최단 거리와 같은 부분을 출력하였다.

파이썬 문법 궁금한게 많아 탐구하였다

우선 global 왜 외부 변수를 쓰는데 이코테에선 global을 사용하지 않았을까..

구글링해도 잘 못찾겠어서 혼자 탐구해봤다.

그냥 바로 함수내에서 전역 변수를 쓰면 참조가 가능하다.

그런데 같은 이름으로 변수를 사용하면 지역변수로 사용이 된다.