사부작사부작해요

도서 '이것이 취업을 위한 코딩테스트다 with 파이썬'의 Chapter 9에 수록된 문제는 플로이드 워셜로 풀이된다. 물론 노드와 간선의 개수가 각각 100개 이하이므로 플로이드 워셜로 풀어도 문제 없다. 하지만 BFS로 풀 수도 있으며, 더 빠르게 동작한다. 노드의 개수 V, 간선의 개수 E인 그래프가 주어진다고 가정하자. 플로이드 워셜로 풀면 시간 복잡도가 O(V^3)이지만 BFS로 풀면 O(E) = O(V^2)이다. 어떻게 BFS로 풀이될 수 있지? 간선의 가중치가 모두 1이기 때문이다. 즉, 노드간 이동 횟수가 이동 거리이다. 특정 노드에서 다른 노드로 이동할 때 마다 큐에 넣으면, 자연히 이동 거리가 짧은 노드들이 큐의 앞에 위치하게 된다. 목적 노드를 꺼낼 때 까지 과정을 반복하면 된다. 간..