백준 10335 There is No Alternative

https://www.acmicpc.net/problem/10335

자력솔한건 아니지만, 그래서 교훈이나 정리할 겸 씁니다.
사실 시험기간이라 글 쓰는게 더 재밌어요 XDD

문제를 보면 상황은 모든 섬을 이을 다리를 최소비용으로 선택하려고 합니다.
즉 MST를 만들어야하는데, 문제 요구는 MST에 필수적인 간선을 구하는 것입니다.

제 첫번째 시도 (결과: TLE)

크루스칼에서 관찰한 내용은

“어떤 간선이 MST에 필수적이라는 것은, 그 간선이랑 같거나 적은 비용의 다른 간선들로 두 정점 $u, v$ 사이 경로를 만들 수 없다는 것이다” 입니다.

1. (크루스칼 알고리즘 설명) 크루스칼 알고리즘에선 간선을 비용으로 정렬하고 비용이 적은 순으로 뽑아서 적용하거나 버립니다. 버리는 기준은 간선을 뽑은 시점에서 뽑은 간선이 잇는 두 정점 사이 경로의 존재 여부입니다. 이때, 같은 비용의 간선 사이엔 뽑는 순서가 상관없습니다.

2. 그렇다면 어떤 간선의 비용이 $c$ 라면, 그 간선을 제외한 $c$ 이하의 모든 간선을 먼저 다 뽑으면, 해당 간선이 MST에 필수적인지 알 수 있습니다.

그런데 2번을 잘 구하는게 어렵습니다.

• 단절선을 전부 구하는 알고리즘으로 구한다 $\rightarrow$ 모든 $c$ 마다 알고리즘을 수행해야하므로 너무 오래 걸림
• 해당 간선빼고 $u$ 에서 시작해 DFS 돌린다 $\rightarrow$ $E$ 번 DFS 돌려야하므로 너무 오래 걸림

AC

$E$번 DFS 돌리면 $O(E^2)$ 이라 시간 내에 안돌아갔습니다.
그런데, MST를 처음에 한 번 만들면서 채택되지 않은 간선들은 자명하게 대체 가능한 간선입니다.
그런데 스패닝 트리의 간선 개수는 $V-1$ 개입니다. 따라서 나머지 간선은 체크할 필요 없습니다. 아래의 풀이에서는 이에 $O(VElogV)$ 에 해결할 수 있습니다.(= $O(ElogV)$ 시간의 유니온-파인드 구조를 쓸 때)

제가 참고한 풀이는

$V-1$ 개의 대체 불가능한 간선 후보들을 Ec 라고 하자.

for e in Ec:
  cost_sum = MST_without(e)
  if cost_sum != 최소비용:
    대체불가능한 간선.insert(e)

위 방법으로 해결할 수 있습니다.

여담

사실 그래프 문제를 별로 안풀어봐서 $O(E)$ 를 $O(V)$ 로 줄이는 아이디어를 접해본 적이 없었습니다. 범부에겐 어려웠다… 저런 접근도 필요하단 교훈을 얻고 가네요.

그리고 사실 $O(VElog*V)$ 가 된다면? 그럼 DFS를 V번 돌리면 되지 않나? 싶어서 짜봤는데 TLE 나네요. 너무 슬프다
나중에 다시 보고 문제점을 다시 찾아봐야겠어요.