6일차 - 노드의 거리

from collections import deque

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.visited = [0] * size
        self.predecessor = [0] * size
    
    def addEdge(self, v1, v2):
        self.matrix[v1][v2] = self.matrix[v2][v1] = 1
    
    def BFS(self, start, goal):
        q = deque([start])
        self.visited[start] = 1

        while q:
            k = q.pop()
            for i in range(self.size):
                if self.matrix[i][k] == 1 and self.visited[i] == 0:
                    self.visited[i] = 1
                    q.appendleft(i)
                    self.predecessor[i] = self.predecessor[k] + 1
        
        return self.predecessor[goal]

for t in range(int(input())):
    v, e = map(int, input().split())
    g = Graph(v)

    for _ in range(e):
        v1, v2 = map(int, input().split())
        g.addEdge(v1-1, v2-1)

    start, goal = map(int, input().split())
    print(f"#{t+1} {g.BFS(start-1, goal-1)}")

 

기본적인 BFS 최단거리 문제이다~ 매우 쉬움!!