BOJ 18193 - 비행기 타고 가요

이 문제는 세그먼트 트리를 이용해 그래프 간선 줄이기 예제 문제로 유명한 문제입니다. 하지만, 이 테크닉 없이 해결하는 방법을 소개해 보고자 합니다.

 

문제를 요약하자면 $1$부터 $N$까지의 숫자를 가진 정점이 존재하고, $[B,C]$에 속하는 모든 정점에서 $[D.E]$에 속하는 모든 정점으로 가는 가중치 $A$인 간선이 $M$개 존재할 때, 각 정점의 최단 경로 길이를 구하는 문제입니다.

 

위에서 설명한 테크닉을 이용하면 $O(N log^2{N})$ 시간복잡도로 해결할 수 있는데 $O(N log{N})$으로도 해결할 수 있습니다.

 

일단, std::priority_queue를 사용하지 않고, 세그먼트 트리만으로 최단 경로 문제를 해결하는 방법을 살펴보겠습니다. 사실 기본적인 원리는 동일하지만, 정점마다 활성 상태와 현재 최단 경로를 저장하고 세그먼트 트리를 이용해서 연산을 빠르게 하는 방법으로 구현합니다.

 

다익스트라 알고리즘은 priority_queue에서 최단 경로가 가장 작은 정점을 꺼내, 연결된 정점들의 최단 경로를 갱신하는 방식입니다. 여기서 "현재 priority_queue에 있는 정점인지?"를 활성 상태로 정의할 수 있습니다. 처음에 시작 정점을 제외한 모든 정점의 최단 경로를 inf로 설정하고 활성 상태를 $1$로 설정해도 무방합니다.

 

이후 아래 과정을 반복합니다.

1. 활성 상태가 $1$인 정점 중, 최단 경로가 가장 작은 정점을 선택합니다. 
2. 해당 정점의 활성 상태를 0으로 업데이트합니다.
3. 선택한 정점과 연결된 정점들의 최단 경로를 갱신합니다.
4. 만약 활성 상태가 $1$인 정점이 없거나, 접근이 불가능하다면 반복을 종료합니다.

여기서 활성 상태가 $1$인 정점 중, 가장 최단 경로를 선택하는 연산과 정점의 최단 경로를 갱신하고 접근하는 연산은 세그먼트 트리를 활용하면 효율적으로 처리할 수 있습니다. 구체적으로, 세그먼트 트리에 $\{$ 활성 상태, 최단 경로, 정점 번호 $\}$를 저장하고 적절한 비교 함수를 만들면 각 연산을 $O(log{N})$ 시간복잡도로 시행해 줄 수 있습니다.

 

결국 구현도 더 귀찮고 시간복잡도도 상수가 더 크지만 $O(M log{N})$ 시간복잡도로 최단경로 문제를 해결해 줄 수 있습니다. 

이 코드는 이 방법을 이용한 1753 최단경로 문제의 코드입니다.

 

굳이 이런 방식을 이용하는 이유는 이것을 느리게 갱신되는 세그먼트 트리로 바꾸면 구간 업데이트도 $O(log{N})$ 시간복잡도로 가능하기 때문입니다. 만약 어떤 정점에서 $[L, R]$ 구간으로 가는 간선이 있으면 해당 구간의 정점들의 최단 경로를 $O(log{N})$ 시간복잡도로 갱신해 줄 수 있습니다. 

 

이 방식대로 풀린다면 좋겠지만, 비행기 타고 가자 문제는 간선의 시작 또한 구간으로 주어진다는 점에서 더 복잡합니다. 즉, 어떤 노드 $X$가 선택되었을 때, $X \in [B, C]$인 간선들을 모두 찾아야 한다는 점이 문제를 어렵게 만듭니다. 최악의 경우, 한 노드의 갱신을 위해 모든 간선을 확인해야 하므로 $O(MN)$의 시간이 걸릴 수도 있습니다. 하지만 다익스트라 알고리즘의 특성상 각 간선은 최대 1회 이하로만 사용됩니다. 따라서 한 번 사용한 간선들은 다시 사용할 필요가 없으므로, 처리 후 즉시 제거하면 비효율적인 반복을 방지할 수 있습니다.

 

이 문제도 세그먼트 트리에 벡터를 저장하는 방식으로 해결할 수 있습니다. 일반적인 세그먼트 트리와는 조금 다르지만, 어떤 구간을 최대 $O(\log{N})$개의 노드로 나누는 방법이 필요했고, 이는 세그먼트 트리의 원리를 활용하여 해결할 수 있으므로 세그먼트 트리를 이용했다고 하겠습니다.

 

어떤 간선이 $[B, C]$ 구간에서 시작될 때, 해당 간선의 번호를 최대 $O(log{N})$개의 노드에 나누어 저장합니다. 이후 노드 $X$가 선택되었을 때, $X$를 포함하는 구간을 대표하는 모든 노드들을 조회합니다. 해당 노드에 저장된 간선들을 하나씩 제거하면서, 아직 사용되지 않은 간선이라면 이를 레이지 세그먼트 트리를 이용해 갱신해 줍니다.

 

결국, 세그먼트 트리의 모든 노드에 저장된 정보의 개수 합이 $O(M \log{N})$ 이하이며, 레이지 연산도 $O(M)$ 이하로 호출되므로 최종 시간복잡도는 $O(M \log{N})$으로 해결할 수 있습니다.

구현은 이 코드를 참고해 주세요.

 

 

가장 오래된 2개의 제출은 세그다익 테크닉을 이용한 코드고 두 번째가 간선을 세그에 저장하는 방식을 재귀로 처리한 코드, 첫 번째가 이를 비재귀로 바꾼 코드입니다. 아무래도 제가 비효율적으로 짜서 시간복잡도가 더 낮음에도 불구하고 실행 시간 1위는 못 먹은 것 같습니다.