[백준][파이썬]14496번: 그대, 그머가 되어

문제 출처 : https://www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

내 풀이

import heapq
import sys
INF = int(1e9)

input = sys.stdin.readline

a, b = map(int, input().split())

n, m = map(int, input().split())

graph =[[]for i in range(n + 1)]

distance = [INF] * (n + 1)

for _ in range(m):
    c, d = map(int, input().split())
    graph[c].append(d)
    graph[d].append(c)
    
def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    if start == end:
        return 0
    
    while q:
        dist, now = heapq.heappop(q)

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

print(dijkstra(a, b))

설명

기본적인 다익스트라 최단거리 알고리즘의 구조에서 벗어나지 않는다.

단 시작점과 도착점을 모두 다익스트라 함수에 매개변수로 넣어준 후에 

경로를 거치며 만약 도착점에 도달한 경우 바로 cost를 리턴하여 함수를 종료하도록 했다.

만약 이 때 종료되지 않고 끝까지 반복문을 돌 경우 -1을 리턴하도록 했다.