[백준_2644] 촌수계산 by python ( BFS )

문제

접근법

코드

import collections
 
def bfs(v):
    q = collections.deque() # 앞,뒤로 삽입 삭제가 가능한 deque
    visited = [False]*(n+1) # visited 를 false로 초기화
    q.append(v) # v를 deque에 삽입
    visited[v] = True # v를 True로 전환
    level = 0
    while q:
        level += 1 # 큐의 길이만큼 while
        for _ in range(len(q)): 
            v = q.popleft() # 큐를 맨 앞에서 제거하고, v를 담는다.
            if v == end: # 나간 v가 end랑 같으면 
                return level - 1 # level을 -1하고 출력
            for j in relation[v]: # v와 인접한 사람 중
                if not(visited[j]):  # 방문이 없으면
                    visited[j] = True
                    q.append(j) # 큐에 담는다 
    return -1
 
n = int(input())
start, end = map(int, input().split())
m = int(input())
relation = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    relation[a].append(b)
    relation[b].append(a)
 
print(bfs(start))