Queue - 노드의 거리

방문한 노드를 체크해주는 기본값 0의 리스트(visit), 각 노드까지의 길이를 저장하는 리스트(cnt)를 활용한다.
여기서 deque는 이동 노드를 저장하는 역할을 한다.

from collections import deque

def bfs(num):
    global res
    q.append(num)
    visit[num]=1
    
    while q:
        node = q.popleft()
        for i in arr[node]:
            if visit[i]==0:
                q.append(i)
                visit[i]=1
                cnt[i]=cnt[node]+1
                if i==end:
                    res= cnt[i]
                    return
        


for tc in range(1, int(input())+1):
    V,E = map(int,input().split())
    arr=[[]*(V+1) for _ in range(V+1)]
    visit=[0]*(V+1)
    cnt=[0]*(V+1)
    
    for i in range(E):
        x,y = map(int,input().split())
        arr[x].append(y)
        arr[y].append(x)
    start,end = map(int,input().split())
    
    res=0
    q=deque()
    bfs(start)
    
    print(f'#{tc} {res}')