Chapter 09, 미래 도시 다른 풀이

[yuna1212]

간선 가중치가 1이기 때문에 BFS로 더 빠르게 풀이할 수 있을 것 같습니다. 이 경우 큐에 넣고 빼기 위한 연산이 최대 간선의 개수만큼 반복되므로 시간 복잡도는 O(E)=O(V^2)입니다. 이 풀이도 적절한가요??

from collections import deque
 
def get_distance(graph, start, destination):
    """ BFS로 최단 거리 구하기 """
    queue = deque([(start, 0)])
    visited = set()
    while queue:
        here, distance = queue.popleft()
        if here == destination:
            return distance
        if here not in visited:
            visited.add(here)
            for next in graph[here]:
                queue.append((next, distance + 1))
    return -1
 
# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
x, k = map(int, input().split())
 
# 출력
meetting_distance = get_distance(graph, 1, k)
if meetting_distance > -1:
    dating_distance = get_distance(graph, 1, x)
    if dating_distance > -1:
        print(meetting_distance + dating_distance)
    else:
        print(-1)
else:
    print(-1)