각각의 버스 구간을 정점으로 두고, 만나는 두 버스 구간 사이에 간선을 두어, 그래프로 나타낼 수 있다. 또한, 버스 구간을 나타내는 정점들 중 출발점을 포함한 정점들을 출발 정점들이라 하고 (하나 이상 존재할 수 있음), 도착점을 포함한 정점들을 도착 정점들이라 한다 (하나 이상 존재 가능). 이 때, 최소한의 버스를 이용하기 위해서는 가장 짧은 <출발 정점 – 도착 정점> 경로를 찾으면 된다.

간선의 길이가 모두 1임을 이용하면, 너비우선탐색(BFS) 알고리즘으로 O(p+q) 시간에 해를 구현할 수 있다. 여기서 p는 정점의 수이고 q는 간선의 수이다.

최단경로 알고리즘(Dijkstra 알고리즘)을 이용하여 O(p²) 시간에 해결할 수도 있다.

koi 버스 갈아타기 문제 풀이