BOJ 18193번: 비행기 타고 가요

개요

- 알고리즘 분류: Dijkstra, Merge Sort Tree, Segment Tree Lazy Propagation

- 문제에 대한 평가: 2차원을 관리하는 효과적인 자료구조에 대한 시사점을 제공함. 아이디어가 기발함. 구현이 상당히 많음.

 

문제 요약

N개의 정점이 있는 그래프에서 간선 M개가 다음과 같이 주어진다.

(cost, s1, s2, e1, e2): 모든 s1 이상 s2 이하의 정점에서 모든 e1 이상 e2 이하의 정점으로 가는 가중치 cost의 간선이 있다.

V에서 각 정점까지의 최단 거리를 구하라.

 

문제 풀이 과정

먼저, s1을 인덱스로 삼고 s2에 대해 정렬하는 Merge Sort Tree를 만든다.

Dijkstra를 수행하되, 티켓을 정점으로 생각한다. 이때 (e1, e2)로 갈 수 있으면 (s1, s2)와 (e1, e2)의 공통부분이 있는 모든 (s1, s2)에 해당하는 티켓을 priority queue에 넣는다. 이 과정은 Merge Sort Tree에서 s1 <= e2인 부분에서 s2 >= e1 에 해당하는 티켓들을 priority queue에 넣음으로써 수행된다. 이를 반복하고 정답을 세그먼트 트리에 저장하는데, 구간 정답 업데이트를 하므로 lazy propagation을 사용한다.

Merge Sort Tree에서는 해당구간에서 s2>=M이면 모두 처리를 한 최소의 M을 저장한다. 모두 처리하기 시작한 곳이 s1마다 다른지 같은지도 저장한다. s1마다 다르다면 트리의 자식 정점들을 호출해야 하고, s1마다 같다면 거기서 모두 저장을 하면 된다. 이로써 priority queue에 중복하여 저장되는 것을 피한다.

나는 처음에 단순히 현재 거리가 작은 것부터 priority queue에 저장했다가, 그러면 Dijkstra의 특성상 priority queue에 한번씩만 들어가서는 정답을 구할 수 없으므로 틀렸다. 이 문제에서는 티켓을 간선으로 보므로 이동 이후의 거리가 정해져 있어서, 이동 이후의 거리 기준으로 저장하면 정답이 된다.

 

배운 점

순서쌍을 관리하는 자료 구조에는 Merge Sort Tree가 있다.

갱신이 완료된 지점을 저장해 둘 수 있다.

구간 쿼리가 없는 경우 구간의 시작과 끝이 동일하지 않은 칸을 lazy로 사용하여 배열 하나로 lazy propagation을 수행할 수 있다.

두 정점을 하나로 생각하여 간선의 개수를 줄이고 Dijkstra 알고리즘을 적용할 수 있다. (티켓 기준으로 생각하였기 때문에 같은 구간 내에서 이동 같은 것들을 고려할 필요가 없었다.)

Dijkstra 알고리즘은 본래 우선순위 큐에 점들이 각각 한 번씩만 들어간다는 보장이 없다. (매우 당연한 이야기이지만 나는 이걸 헷갈려서 1시간 가까이 틀리고 있었다...)