[백준] 2644 파이썬(python) : 촌수계산 - (visit과 cnt의 차이)

2644번: 촌수계산

 

 

import sys
from collections import deque
n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)
visit = [0]*(n+1) #1
def bfs():
    q = deque()
    q.append(a)
    while q:
        x = q.popleft()
        if x == b:
            return visit[b]
        for i in graph[x]:
            if not visit[i]:
                visit[i] = visit[x] + 1
                q.append(i)
    return -1
print(bfs())

 

#1 : cnt가 아닌 visit리스트에 1을 추가하는것은 cnt를 +1 추가 하면서 너비우선탐색을하면 원하는 값을 얻지 못하는 상황이기 때문이다.

 

어느쪽에서 시작해도 상관없다. 결국 입력받은 두 노드가 이어져 있다는것만 증명하면된다. 이어져 있지 않다면 -1을 출력한다.