[SWEA] 5102 [파이썬 S/W 문제해결 기본] 6일차 - 노드의 거리

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

# 문제 링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg&&# 

SW Expert Academy

# Soultion

최소거리를 구하는 문제이므로 bfs를 사용

from collections import deque           
t = int(input())    
for tc in range(1,t+1):
    v,e = map(int,input().split())
    graph = [[]for _ in range(v+1)]
    for _ in range(e):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    s,g =map(int,input().split())
 
    queue = deque([s])
    visited = [0]*(v+1)
    visited[s]=1
    while(queue):
        n = queue.popleft()
        for i in graph[n]:
            if visited[i]==0:
                queue.append(i)
                visited[i] = visited[n]+1
 
    if visited[g]!=0:
        print("#"+str(tc),visited[g]-1)
    else:
        print("#"+str(tc),0)