서론
문제를 풀다보면, 그래프로 모델링해서 해결하는 문제를 자주 만날 수 있습니다.
이 글에서는 세그먼트 트리를 이용해 특정 형태의 그래프의 간선 개수를 $O(K)$에서 $O(\log K)$ 내지는 $O(\log^2 K)$정도로 줄이는 방법과 여러가지 예시 문제를 소개합니다.
(최단경로) BOJ 18193 비행기 타고 가요 (2019 경기과고 송년대회)
Naive 풀이
Naive한 풀이는 간단합니다. 각 티켓마다 아래 코드를 반복해서 그래프를 만든 뒤, 다익스트라 알고리즘을 이용해 최단 거리를 구해주면 됩니다.
최악의 경우 정점 $N$개, 간선 $O(MN^2)$개가 만들어지기 때문에 시간초과가 납니다.
1 | |
풀이
간선이 $O(MN^2)$개 만들어지는 이유를 생각해봅시다.
각 티켓마다 $i \in [b, c], j \in [d, e]$인 모든 $(i, j)$에 대해 $i$에서 $j$로 가는 간선을 추가하게 됩니다. 구간 $[b, c]$와 구간 $[d, e]$의 크기가 최대 $O(N)$이기 때문에 한 티켓 당 최대 $O(N^2)$개의 간선이 만들어지게 됩니다.
구간을 더 적은 정점으로 표현할 수 있다면, 더 적은 간선만으로 그래프를 구축할 수 있게 됩니다. 만약 크기가 $x$인 구간을 $f(x)$개의 정점으로 표현할 수 있다면 ${f(x)}^2$개의 간선을 만들게 됩니다.
세그먼트 트리는 임의의 구간을 $O(\log N)$개의 정점으로 나타내는 자료구조입니다. 이런 세그먼트 트리의 성질을 이용하면 $O(\log^2 N)$개의 간선만으로 그래프를 만들 수 있게 됩니다.
이렇게 그래프를 만듭시다. 하늘색 정점이 실제 도시를 나타내는 정점이고, 나머지 정점들은 세그먼트 트리를 구축하기 위한 가상의 정점들입니다. $[2, 6]$에서 $[4, 8]$로 가는 티켓을 만들어봅시다.
노란색 정점들만 선택해주면 분홍색 정점들도 모두 선택한 효과를 얻을 수 있습니다. 왼쪽 트리와 오른쪽 트리에는 각각 $O(\log N)$개의 노란색 정점들이 존재합니다.
아래 그림처럼 왼쪽 트리와 오른쪽 트리에 있는 노란색 간선들을 서로 이어주면 $O(\log^2 N)$개의 간선만 만들게 됩니다.
$O(N)$개의 정점, $O(N + M \log^2 N)$개의 간선으로 이루어진 그래프에서 다익스트라 알고리즘을 수행하므로 $O(N \log N + M \log^3 N)$에 문제를 해결할 수 있습니다.
(2-SAT) AtCoder ARC 069 F. Flags
문제 요약
수직선 상에 $N$개의 깃발을 설치해야 하고, $i$번째 깃발은 $x_i$ 혹은 $y_i$에 설치할 수 있습니다.
$N$개의 깃발을 적절히 설치했을 때, 깃발 사이의 거리의 최솟값을 최대화시키는 문제입니다.
Naive 풀이
모든 깃발 사이의 거리가 $d$ 이상이 되도록 설치할 수 있는지 판별하는 결정 문제를 풀 수 있다면, 파라메트릭 서치를 이용해 문제를 풀 수 있습니다. 이러한 결정 문제는 2-SAT을 이용해 풀 수 있습니다.
그래프를 Naive하게 만들 경우, 간선은 최대 $O(N^2)$개 만들어집니다.
풀이
간선의 개수를 줄여봅시다.
깃발들을 위치 순으로 정렬합시다. 어떤 깃발 $i$를 선택하면 구간 $[s_i, e_i]$에 있는 모든 깃발을 선택하면 안 된다고 생각할 수 있습니다.
위에서 설명했던 ‘비행기 타고 가요’ 문제처럼 세그먼트 트리를 이용해 구간을 $O(\log N)$개의 정점으로 표현해주면 간선을 $O(N \log N)$개만 만들어서 문제를 풀 수 있습니다.
(위상정렬) BOJ 18362 Desert (POI 2014/2015 Stage 2)
문제 요약
길이 $N$짜리 수열 $A$가 있습니다. $S$개의 원소는 정확한 값이 주어지고, 아래와 같은 $M$개의 정보가 추가로 주어집니다.
- $l\space r\space k\space x_1\space x_2\space \dots x_k$ : $\displaystyle \min_{i\in { x_1, x_2, \dots, x_k }} (A_i) \geq \max_{i\in [l, r], i\not\in { x_1, x_2, \dots, x_k }} (A_i)$
모든 원소가 $1$ 이상 $10^9$ 이하의 자연수인 수열 $A$가 존재한다면 TAK을 출력하고 그러한 수열을 아무거나 출력합니다. 존재하지 않는다면 NIE를 출력합니다.
Naive 풀이
$\displaystyle \min_{i\in { x_1, x_2, \dots, x_k }} (A_i) \geq \max_{i\in [l, r], i\not\in { x_1, x_2, \dots, x_k }} (A_i)$는 모든 $A_j$가 모든 $A_i$보다 작다는 것을 의미합니다.
더미 정점(0번 정점이라고 합시다.)을 하나 만들어줍시다.
정확한 값이 주어진 주어진 $S$개의 원소에 대해서는 $0$번 정점에서 $i$번 정점으로 가는 가중치가 $A_i$인 간선을 만들고, 나머지 정점들에 대해서는 가중치가 1인 간선을 만듭시다.
$O(N)$개의 간선을 만들게 됩니다.
$i \in {x_1, x_2, \ldots, x_k}, j \in [l, r], j \not\in {x_1, x_2, \ldots , x_k}$인 모든 $i, j$에 대해 $j$에서 $i$로 가는 가중치가 0인 간선을 만듭시다.
최대 $O(N^2)$개의 간선을 만들게 됩니다.
이렇게 만들어진 그래프가 있을 때, 0번 정점에서 각 정점으로 가는 최장 경로를 구하면 답을 구할 수 있습니다.
사이클이 만들어지는 등 모순이 생기는 경우, NIE를 출력하면 됩니다.
풀이
위에서 본 문제들과 똑같이 세그먼트 트리를 이용해 구간을 $O(\log N)$개의 정점으로 나타내주면 되긴 합니다.
$x_1, x_2, \ldots, x_k$가 구간 $[l, r]$ 안에 있을 수 있다는 것을 처리하는 것이 귀찮습니다. 일단 $x_i$가 구간 $[l, r]$ 내부에 있다면, 구간을 적절히 쪼개줍시다. 이렇게 쪼개진 구간을 $[l_1, r_1], [l_2, r_2], \ldots , [l_t, r_t]$라고 합시다.
구간 $[l_j, r_j]$에서 $x_i$로 가는 간선을 모두 만들어야 합니다.
세그먼트 트리를 이용해 각 구간을 $O(\log N)$개의 정점으로 나타낸다고 하더라도, 구간이 최대 $O(K)$개 존재할 수 있기 때문에 간선을 $O(K^2 log K)$개나 만들게 됩니다.
이 문제를 해결하기 위해 더미 정점을 추가로 만듭시다.
(1) 구간 $[l_j, r_j]$에서 더미 정점으로 가는 간선을 모두 만들고, (2) 더미 정점에서 $x_i$로 가는 간선을 만들면 됩니다.
(1)에서 $O(\log N)$개의 간선을 만들고, (2)에서 $O(K)$개의 간선을 만들게 됩니다.
세그먼트 트리를 만드는데 정점 $O(N)$개, $M$개의 추가 정보를 표현하는데 더미 정점 $O(M)$개가 필요해서 총 $O(N+M)$개의 정점이 필요합니다.
세그먼트 트리를 만드는데 간선이 $O(N)$개, $M$개의 추가 정보를 표현하는데 간선 $O(K + M \log N)$개가 필요해서 총 $O(N + K + M \log N)$개의 간선이 필요합니다.
위상정렬만 돌리면 되므로 $O(N+K+K \log N)$에 문제를 해결할 수 있습니다.