[백준 BOJ] 3176. 도로 네트워크
12 Jul 2022난이도
Platinum IV
문제 풀이
\(\scriptsize N\)개의 도시에 \(\scriptsize N - 1\)개의 도로가 있고, 어느 두 도시를 골라도 해당 도시를 잇는 경로가 존재한다는 점에서 그래프가 트리로 고정된다.
\(\scriptsize K\)개의 쿼리가 주어지고, 각 쿼리는 두 노드를 연결하는 경로 위에 존재하는 엣지들 중, 가장 짧은 것과 가장 긴 것을 찾는 것이라 생각할 수 있다.
Naive하게 생각하면, 쿼리가 주어질 때마다 경로를 전부 탐색해주면 된다. 이 방법으로 문제를 해결할 경우 쿼리 당 \(\scriptsize O(N)\)이다. 그러나, 아쉽게도 총 시간복잡도가 \(\scriptsize O(KN)\)이니 시간초과를 받는다. 그러면, 쿼리 당 \(\scriptsize O(N)\)보다 빠르게 처리해야 한다는 의미이다. \(\scriptsize O(log N)\) LCA와 희소 배열을 사용하면, 쿼리 당 \(\scriptsize O(log N)\)으로 처리할 수 있다.
\(f(i, j) :=\) “\(i\)번 노드에서 \(2^{j}\)번 루트 쪽으로 이동할 때, 찾을 수 있는 가장 짧은 도로의 길이”
\(parent(i, j) :=\) “\(i\)번 노드의 \(2^{j}\)번째 부모 노드”
라고 정의하자. \(\scriptsize 2^{j} = 2^{j - 1} + 2^{j - 1}\) 라는 점을 생각하면 다음 같은 관계식을 유도할 수 있다.
\[f(i, j) = \min(f( parent(i, j - 1), j - 1), f(i, j - 1))\]
\(\scriptsize 2^{j - 1}\)번째까지 최솟값과 \(\scriptsize 2^{j - 1}\)번째부터 \(\scriptsize 2^{j}\)까지의 최솟값을 비교해서 작은 값이 \(\scriptsize f(i, j)\)이 되기 때문이다. 이 논리를 가장 긴 도로의 길이를 구하는데에도 그대로 적용시킬 수 있다. 이를 미리 전처리 해두면 공간복잡도 \(\scriptsize O(NlogN)\), 전처리 하는데 시간복잡도 \(\scriptsize O(NlogN)\) 이고 LCA를 활용해 쿼리 당 \(\scriptsize O(log N)\)에 처리 가능하다. 따라서 총 시간복잡도 \(\scriptsize O(NlogN + KlogN)\)에 해결 가능하다.
for(int j = 0; j < sz; ++j) {
for(int i = 1; i <= N; ++i) {
if(parent[i][j] == -1) continue;
parent[i][j + 1] = parent[ parent[i][j] ][j];
max_dist[i][j + 1] = max(max_dist[i][j], max_dist[ parent[i][j] ][j]);
min_dist[i][j + 1] = min(min_dist[i][j], min_dist[ parent[i][j] ][j]);
}
}
dfs를 이용해 \(\scriptsize j = 2^{0}\)에 대한 값을 모두 채워준 후, 위 코드처럼 배열들을 전처리해주고 LCA를 잘 이용해서 답을 구해주면 된다.