[SWEA 5102번] 노드의 거리

from collections import deque

t = int(input())

answer = []

for _ in range(t):
    v, e = map(int,input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0]*(v+1)

    for i in range(e):
        start, end = map(int,input().split())
        graph[start].append(end)
        graph[end].append(start)

    s, g = map(int,input().split())

    def bfs(s,g):
        visited[s] = 0

        queue = deque([s])

        while queue:
            v = queue.popleft()

            for node in graph[v]:
                if visited[node] == 0:
                    if node == g:
                        return visited[v]+1
                    queue.append(node)
                    visited[node] = visited[v]+1
        
        return 0
    
    answer.append(bfs(s,g))

for i,value in enumerate(answer):
    print(f"#{i+1} {value}")

이번 문제는 V개의 노드와 방향성이 없는 E개의 간선들이 주어졌을 때, 출발 노드에서 도착 노드까지 거쳐야 하는 최소 간선 개수를 구하는 문제이다.

 

2차원 인접 리스트 형식으로 그래프를 표현하고 BFS를 사용하면 어렵지 않게 풀 수 있는 문제인데, 다만 조심해야 할 것은 초기에 그래프 정보를 입력할 때 "양방향"으로 저장해주어야 한다는 것이다 :)