이코테 최단 경로 미래 도시 - 문제 다른 풀이, BFS

도서 '이것이 취업을 위한 코딩테스트다 with 파이썬'의 Chapter 9에 수록된 문제는 플로이드 워셜로 풀이된다. 물론 노드와 간선의 개수가 각각 100개 이하이므로 플로이드 워셜로 풀어도 문제 없다.

 

하지만 BFS로 풀 수도 있으며, 더 빠르게 동작한다.

 

노드의 개수 V, 간선의 개수 E인 그래프가 주어진다고 가정하자. 플로이드 워셜로 풀면 시간 복잡도가 O(V^3)이지만 BFS로 풀면 O(E) = O(V^2)이다.

어떻게 BFS로 풀이될 수 있지?

간선의 가중치가 모두 1이기 때문이다. 즉, 노드간 이동 횟수가 이동 거리이다.

특정 노드에서 다른 노드로 이동할 때 마다 큐에 넣으면, 자연히 이동 거리가 짧은 노드들이 큐의 앞에 위치하게 된다. 목적 노드를 꺼낼 때 까지 과정을 반복하면 된다.

 

간선의 가중치가 1이 아니었다면 BFS로 풀 수 없다.

시간복잡도

노드의 개수가 V, 간선의 개수가 E인 그래프가 주어진다고 가정하자.

플로이드 워셜로 풀면 시간 복잡도가 O(V^3)이다.

 

하지만 BFS로 풀면 O(E) = O(V^2)이다. BFS 과정은 다음과 같다.

(1) 큐에서 노드를 하나 꺼낸다.
(2) 꺼낸 노드와 연결된 노드를 모두 확인하여, 방문하지 않은 노드는 (노드 이름, 거리) 형태로 큐에 넣는다.
(2) 큐가 비거나 목적지에 도달할 때 까지 위 과정을 반복한다.

(1)의 수행 횟수는 최악의 경우 (2)와 동일하다.

(2)의 수행 횟수는 최악의 경우 간선의 개수 E이다. 방문 여부를 따로 저장하기 때문에, 방문한 노드를 다시 방문할 일이 없다. 따라서 큐에 노드를 넣기 위해 연결된 노드를 확인하는 작업은 간선의 개수를 초과하여 수행될 수 없다. 큐에 원소를 넣고 빼는 일은 O(1)이 걸린다.

 

따라서 시간복잡도는,

$$O(E)*O(1)+O(E)*O(1) = O(E) = O(V^2)$$

 

BFS 코드

플로이드 워셜 코드는 이코테 github에서 확인하자.

다음은 BFS로 풀이한 코드이다.

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)

---

REFERENCES

나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬