Baekjoon(백준) 11499번 - Path

백준 사이트의 11499번.
문제 제목 : Path
백준 11499

ICPC Asia Regional 2015 Daejeon G번 문제
convexhull을 이용해야만 할 것 같은 인상을 주지만 약간 다르다.
사실 convexhull을 구하는 Graham’s scan 같은 거를 이용하는 방법이 있을 수 있겠으나 시간복잡도 상으로는 불가능하다. 그래서 Graham’s scan 알고리즘의 아이디어를 약간 차용해서 많이 변형시킨 알고리즘을 고안하였다.

풀이 전략

기본 idea는 아래와 같다.

점 p(k, d)가 도착지점일 때 가장 짧은 polygonal chain에 포함되는 점들은 $v_0, v_i (i > k), p$ 중에만 있다.

이는 문제에서 말하는 것이 histogram 이고, histogram과 문제에서 말하는 shortest polygonal chain을 잘 생각해보면 저런 조건이 성립할 수 밖에 없음을 알 수 있다.
그래서 처음에 생각한 것은 각 도착 지점 p(k, d) 마다 $v_0, v_i (i > k), p$ 에 해당하는 점들에 대해서만 Graham’s scan을 매번 적용해서 convexhull을 구하는 방식이었다. Graham’s scan는 $O(n log{n})$, 이를 M개의 도착지점에 대해 모두 적용하므로 시간복잡도가 $O(nm log{n})$ 이 된다. n과 m 모두 100000이 최대값이므로 주어진 시간 (2초, 약 2억번의 연산 가능) 내에는 불가능하다.
그러면 결국 한 번의 탐색으로 모든 도착 지점에 대해 답을 계산해야 한다는 생각이 들었다. 그래서 histogram의 clockwise 방향으로 점들을 탐색하면서 orientation에 따라 convexhull 에 포함되는 점들을 계속 갱신하고 중간에 도착지점을 만난다면 그 때까지의 convexhull에 있는 점들을 바탕으로 답을 계산하여 더해주는 방식을 생각하게 되었다. 자세한 내용은 구현에 설명해놓았다.
약간 쉽게 생각하면 입력으로 주어진 histogram 모양의 틀이 있고 그 틀의 모서리 위에 도착해야 하는 지점이 있다고 생각할 수 있다. 여기서 $v_0$에 실의 한 쪽 끝을 묶고 팽팽하게 실을 유지하며 각 도착 지점에 다른 한 쪽 끝이 닿게 한다고 생각해보면 문제 상황을 쉽게 이해할 수 있을 것이다. $v_0$에서 도착지점까지 직선으로 그었을 때 틀 밖으로 나가는 부분이 생긴다면 앞에서 얘기한 것처럼 틀 안에서 실로 도착지점까지 팽팽하게 연결했을 때 실이 걸려서 꺾여지는 점이 있을 것이다. 그렇게 껶여지는 부분이 항상 이전의 부분에 비해 다음 부분이 counterclockwise 방향으로 꺾이지 않겠는가? 필자는 그렇게 이 알고리즘을 생각해내었다.

구현

구현방법은 다음과 같다.

1. 도착해야 하는 point들의 좌표를 구하고 histogram의 선을 clockwise로 따라갈 때 거치는 point들의 순서에 맞게 도착해야 하는 point들과 $v_i$를 dots array에 배치 (위의 figure에서 예를 들면 dots array에 들어있는 점들은 $v_0, v_7, v_6, p_4, v_5, p_3, v_4, v_3, p_2, v_2, p_1, v_1$ 순이 될 것이다)
2. dots array를 순서대로 탐색하며
   A. 처음에 convex stack에 $v_0, v_{N-1}$ 추가 (initialize)
   B. 이후 convex stack의 top을 B, top 바로 아래를 A, 그리고 dots array의 현재 element를 C라 할 때 $\vec{AB} \times \vec{AC} > 0$ 이 될 때까지 convex stack에서 pop한 후 C를 stack에 push 함. ($\vec{AB}$ 에 대해 $\vec{AC}$ 의 orientation이 counterclockwise 가 되도록 하는 것) C를 push 할 때는 $\overline{BC}$의 length 값도 같이 저장, convex stack에 있는 vertex 들을 따라 만들어지는 총 distance를 저장하는 total_conv_dist에 $\overline{BC}$ length를 더해줌. pop할 때는 top에 저장되어 있던 길이를 total_conv_dist에서 빼줌.
   C. 만약 도착해야 하는 point를 만나면 point를 convex stack에 추가하고 (위에서 B에 해당) ans += total_conv_dist 함.

위의 구현 방식은 $O(N + M)$ 의 시간복잡도를 가지므로 제한 시간 내에 충분히 실행이 완료된다. solution code는 위의 구현 방법과 완전히 똑같이 구현되어 있음. 참고 바람.

solution code는 아래 링크의 github에 있다.

baekjoon 11499 solution code

P.S. 여담

이제 2주 뒤면 나는 학교도 휴학하고 잠시 모험을 떠날 예정이다. ‘모험’이라 하는 이유는 정확한 사유를 공개적으로 말할 수 없기 때문이다. 떠나기 전 논문 리뷰나 백준 PS 관련 포스트를 한 번 더 올리거나 아니면 안 올리고 바로 갈 것 같다. 아마도… 약 2년 조금 뒤에 돌아올 것이다.