티스토리 뷰

해법

[HackerRank w7] Savita And Friends

전명우 2014.07.21 21:32

문제: HackerRank or hongjun7's blog


이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다.


우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다.


답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다.


답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다.


문제에서 설명한데로 $K$번째 간선은 $A$와 $B$를 잇는 간선이며, 길이가 $C$라고 하자.

$D_i$를 $A$에서 점 $i$로 가는 최단 거리라고 정의하고,

$E_i$를 $B$에서 점 $i$로 가는 최단 거리라고 정의하자.

이들은 다익스트라 알고리즘(Dijkstra Algorithm)을 통해 $O(N \log_2 N)$ 혹은 $O(N \log_2 M)$ 만에 구할 수 있다.


점 $P$에서 정점 $i$까지 이동 거리 $d$안에 도착 가능한 $P$의 위치들은 최대 2개의 구간으로 표현 가능하다.

정점 $A$에서 점 $P$ 까지의 거리를 $x$라 하자.


1) 점 $P$에서 정점 $A$를 통해 정점 $i$로 가는 경우

만약, $D_i + x > d$ 인 경우 불가능하다.

그렇지 않다면, $0 \leq x \leq d - D_i$를 만족하는 $x$에 대응하는 $P$의 위치가 가능하다.


2) 점 $P$에서 정점 $B$를 통해 정점 $i$로 가는 경우

만약, $E_i + C - x > d$ 인 경우 불가능하다.

그렇지 않다면, $E_i + C - d \leq x \leq C$를 만족하는 $x$에 대응하는 $P$의 위치가 가능하다.


정점 $i$에 대해 이동 거리가 $d$ 이하가 가능한 $P$의 위치들을 구했으므로, $N$개의 정점에 대해 모두 가능한 $P$의 위치가 있는지 확인하여주면된다.


이를 좀 더 간단히 구하기 위해, 반대로 불가능한 $P$의 위치들을 구한다.

이는 정점 $i$에 대해 $\max(d - D_i + 1, 0) \leq x \leq \min(E_i + C - d - 1, C)$를 만족하는 $x$에 대응하는 $P$의 위치들이다. 이제 최대 $N$개의 구간들 중에서 모든 구간에 속하지 않은 $x$ 값을 구하면 된다. 이는 매우 잘 알려진 문제이며, $O(N \log_2 N)$ 만에 해결할 수 있다.


코드 보기


저작자 표시
신고

'해법' 카테고리의 다른 글

Central European Olympiad in Informatics 2016  (0) 2016.07.22
[HackerRank w7] The crazy helix  (2) 2014.07.22
[HackerRank w7] Savita And Friends  (0) 2014.07.21
[USACO 2011 February Gold] The Lost Cows  (0) 2011.06.04
[USACO 2008 November Gold] Toys  (0) 2011.06.04
[z-trening] z-dots  (0) 2011.06.02
댓글
댓글쓰기 폼