[백준/Python] #14496 그대, 그머가 되어

문제

알고리즘

전형적인 bfs문제이다. 시작점인 a부터 b까지의 최소거리를 구하면 된다.

각 지점까지의 거리를 -1, 초기값으로 설정하고 a를 시작점으로 하여 bfs를 수행해주면 된다.

bfs를 수행하면서 graph 조건을 보고 거리가 갱신이 안되어있다면 현재 지점까지의 거리+1로 해당 거리를 수정해주면 된다.

코드

import sys
input = sys.stdin.readline
from collections import deque

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

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

distance = [-1] * (n + 1)
q = deque()

if a == b:
    print(0)
else:
    q.append(a)
    distance[a] = 0

    while q:
        v = q.popleft()
        if v == b:
            break

        for i in graph[v]:
            if distance[i] == -1:
                distance[i] = distance[v] + 1
                q.append(i)

    if distance[b] == -1:
        print(-1)
    else:
        print(distance[b])