13141. Ignition

플래티넘 재활중. 물론 쉽지 않다...

13141번: Ignition

---

정점 중 하나에 불을 붙여 그래프를 태울 때, 그래프가 다 타는 시간의 최솟값을 구해야 한다. 일단 지문에서 파악할 수 있는 내용은

• 그래프가 다 타는 최소 시간을 구하기만 하면 된다.
• 불은 1초에 거리 1씩 간선을 태운다.
• 간선의 양 끝에 불이 붙는 경우, 불이 간선의 어느 지점에서 만날 때 불이 꺼진다.
• 불이 정점에 도달하면 정점에 연결된 모든 정점에 즉시 불이 붙는다.

생각 1: 구현

당연히 시간 초과겠지만, 불이 타는 과정을 직접 구현해 보자. 불이 간선의 가운데에서 만날 수 있으므로, 시간의 최소 단위(틱)를 1초가 아닌 0.5초로 잡아야 한다.

 

각 틱마다 현재 불에 타고 있는 간선의 상태를 업데이트하면 그래프가 타는 과정을 구현할 수 있다. 이렇게 하면 그래프가 타는 시간을 $O(M^{2}L)$ 시간에 구할 수 있다. 그래프가 일자로 배열된 최악의 경우 다 타는 데 $ML$ 시간이 걸리고, 이 시간동안 최대 $M$개의 간선을 체크해야 하기 때문이다.

 

결국 모든 정점에 대해 그래프가 타는 시간을 계산하려면 $O(NM^{2}L)$의 시간이 걸린다. 어림도 없다. 아니 알면 하지 말라니까?

생각 2: 똑똑하게

살짝 태그 힌트를 썼다. 다익스트라로 문제를 풀 수 있다고 한다. 흠.. 어떻게?

 

다익스트라를 이용하여 한 정점에서 다른 정점까지의 최소 거리를 구한다. 불이 1초에 1씩 이동하므로 최소 거리는 불이 정점에 도달하는 데 걸리는 시간과 같다. 간선의 양 끝에 불이 도달하는 시간을 알면, 간선이 언제 다 타는지 구할 수 있다. 불이 $i$번 정점에 가장 빨리 도달하는 시간을 $dist[i]$라고 하고, 이제 정점 $a$와 $b$에 연결된 길이 $c$인 간선이 타는 시간을 계산해 보자.

 

간선이 타는 경우에는 크게 두 가지가 있다.

불 하나가 전부 태우는 경우

간선이 정점에서 타기 시작하여 다 탈 때까지 반대쪽 정점에 불이 도착하지 않는 경우이다. 이 경우 간선이 전부 타는 시각은 $min(dist[a], dist[b]) + c$이다.

불이 간선 중간에서 만나는 경우

간선이 타는 도중 반대편 정점에 불이 붙어, 불이 양쪽에서 간선을 태우는 경우이다. 불이 $a$에 먼저 붙는다고 가정하면 대략 다음과 같다.

1. 불이 $a$에 붙는다.
2. 불이 하나만 붙어 있으므로 간선이 초당 1씩 탄다. 따라서 $a$에서 시작된 불은 $\triangle d = dist[b]-dist[a]$만큼 간선을 태운다.
3. 남은 간선의 길이는 $d' = c- \triangle d$이다.
4. 불이 $b$에 붙는다.
5. 불이 양쪽에 붙어 있으므로 간선이 초당 2씩 탄다. 따라서 $\frac{d'}{2}$ 시간 후에 간선이 모두 탄다.

계산하면 간선이 모두 타는 시각은 $dist[a] + \frac{c - \triangle d}{2}$이다.

 

다익스트라의 시간 복잡도가 $O(M logN)$이고, 간선이 모두 타는 시각을 계산하는 데 걸리는 시간 $O(M)$을 합하면 $O(M log N)$ 시간이 걸린다. 따라서 정답은 $O(NM logN)$ 시간에 가능. $N$이 작아서 가능한 방법이다.

---

그냥 구현할 생각만 했는데.. 역시 플레는 다르구만.