[BOJ] [Python] 14496번 : 그대, 그머가 되어

다익스트라 알고리즘을 활용하여 풀었다.

 

 

가중치 값이 1이라서 BFS로 풀어도 무방하다.

 

# N : 문자 개수
# M : 문자쌍
# -1 : 불가능

# a : 시작 지점
# b : 찾는 지점

# 경로 : []
# 값 : [x, 0, 무한, 무한, 무한]

import sys

input = sys.stdin.readline

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

route = []  # 경로

val = [10000000] * (n + 1)  # 값
val[start] = 0

for _ in range(n + 1):
    route.append([])

for _ in range(m):
    num = list(map(int, input().split()))
    route[num[0]].append(num[1])
    route[num[1]].append(num[0])

order = [start]  # 순서 리스트


def Dijkstra():
    while order:

        now = order[0]

        for i in route[now]:

            cal = val[now] + 1

            if i == find:
                return cal

            if cal < val[i]:
                val[i] = cal

                order.append(i)

        order.pop(0)

    return -1


if start == find:
    print(0)
else:
    print(Dijkstra())