BOJ 14496 - 그대, 그머가 되어

문제

백준 온라인 저지 - 14496번

풀이 과정

시작 지점에서 목표 지점에 도달하기 위한 최단 경로를 구하는 문제입니다.

다익스트라 알고리즘 을 활용해서 시작 지점에서 모든 지점까지의 거리를 구할 수 있습니다.

코드

import sys
import heapq

INF = 2e9


def make_graph():
    graph = [[] for _ in range(n + 1)]

    for frm, to in edges:
        graph[frm].append(to)
        graph[to].append(frm)

    return graph


def dijkstra(graph):
    dist = [INF] * (n + 1)
    pq = []

    heapq.heappush(pq, [0, a])
    dist[a] = 0

    while pq:
        cost, here = heapq.heappop(pq)
        if dist[here] < cost:
            continue

        for there in graph[here]:
            next_cost = cost + 1
            if next_cost < dist[there]:
                dist[there] = next_cost
                heapq.heappush(pq, [next_cost, there])

    return dist


def solution():
    graph = make_graph()
    dist = dijkstra(graph)

    return dist[b] if dist[b] != INF else -1


if __name__ == '__main__':
    a, b = list(map(int, sys.stdin.readline().split()))
    n, m = list(map(int, sys.stdin.readline().split()))
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

    answer = solution()
    print(answer)