BOJ 18344. 가장 짧은 순례

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

$G=(V, E)$에서 정점 $1$부터 $N$으로 이동하는 최단거리를 찾아야 한다. 단, 이동 중 시작점과 끝점을 포함해 정확히 여덟 개의 서로 다른 정점을 방문해야 한다.

서브태스크 1 (1점)

방문하는 정점을 $[v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8]$이라고 하고, 이때 사용하는 7개의 간선 번호를 $[e_1, e_2, e_3, e_4, e_5, e_6, e_7]$이라 하자. (단, $v_1 = 1$, $v_8 = N$)

$e_2$를 고정하면 $(v_2, v_3)$ 또는 $(v_3, v_2)$가 고정된다. 마찬가지로 $e_4$와 $e_6$을 고정하면 ${ v_4, v_5 }$와 ${ v_6, v_7 }$이 고정된다. 이제 $[v_1, \cdots, v_8$]로 가능한 수열은 $2^3$개 뿐이므로, 모든 경우를 검사해 보면 된다. 시간 복잡도는 $O(M^3)$이다.

서브태스크 2 (11점)

$e_3$과 $e_5$를 고정하면 ${ v_3, v_4}$와 ${ v_5, v_6 }$이 고정된다. $[v_3, v_4, v_5, v_6]$을 고르는 $2^2$가지 경우를 모두 시도해 보자. 이제 남은 일은 $v_2$와 $v_7$을 고르는 일이다.

사전에 모든 정점 $v$에 대해, $1 \rightarrow x \rightarrow v$로 가는 최단경로 중 가장 짧은 6개를 구해 놓자. $(x \neq N)$ 마찬가지로 $v \rightarrow x \rightarrow N$으로 가는 최단경로 중 가장 짧은 6개도 구해 놓자. 여기서 각각 $v_2$와 $v_7$이 나와야 함을 알 수 있고, ${ v_3, v_4, v_5, v_6 }$ 중에 속하지 않는 것을 제외하고 후보를 가장 짧은 2개씩만 남긴다. 가장 좋은 후보가 같은 $x$를 사용한다면 따로 처리해 주는 등의 방식으로 문제를 단순한 케이스워크로 해결할 수 있다.

시간 복잡도는 $O(N^2 + M^2)$이다. 다만 상수가 조금 크고, 직접 짜 보진 않아서 돌아간다고 확신하진 않는다.

서브태스크 3 (111점)

일단 $e_4$를 고정해 ${ v_4, v_5}$를 고정하고, 2가지 경우를 모두 해 보며 $(v_4, v_5)$가 고정된 상황에서 어떻게 효율적으로 풀지를 생각해 봐야 한다.

앞의 접근과 같이 $1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4$ 부분과 $v_5 \rightarrow v_6 \rightarrow v_7 \rightarrow N$ 부분에서 최단거리 후보를 몇 개 구해놓은 다음, 좋은 것을 골라 쓰는 방법을 사용할 것이다. 대칭적인 상황이므로 $1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4$ 부분을 보자. $v_2$와 $v_3$이 $v_5$, $v_6$, $v_7$ 셋과 겹치는 경우를 모두 피해야 하므로, $v_2$와 $v_3$의 후보를 상수 개 이하로 줄일 수 있음을 알 수 있다. 이해가 잘 되지 않는다면 다음 문제와 같은 방식이라고 생각하면 된다.

• 길이 $N$의 두 수열 $A$와 $B$가 있다. 적당한 $1 \le i, j \le N$을 골라 $A_i + B_j$를 최대화하라. 단, $i \neq j$여야 한다.
  • 풀이: $i$와 $j$로 가능한 후보는 $A_i$와 $B_j$가 가장 큰 두개뿐이다. $A_i$의 경우 $A_i$가 가장 큰 최댓값이 아닌 $i$를 고를 조건은 $B_i$ 역시 최댓값이고 $B_i$를 고르는 게 더 이득인 경우뿐이고, 이 경우는 그 $i$를 제외한 최댓값 인덱스를 골라야 한다.
• 실제 문제는 더 복잡하기 때문에, 후보가 2개보다는 더 많이 필요할 것이라고 추측할 수 있다. 자세한 분석은 나중에 한다.

어려운 부분은 모든 $v_4$에 대해 이 가능한 최적해들을 사전에 전처리해 주는 것이다. 이것을 나이브하게 하면 $O(NM)$에 될 것이다.

 

먼저 모든 $v_3$에 대해 $1 \rightarrow v_2 \rightarrow v_3$ 최단거리 목록을 만들어 두자. 이것은 $O(M)$에 할 수 있다. 단순히 가장 짧은 최단거리만 저장하면 되는 것이 아니라, 후보 여러 개를 저장해 둬야 하는데, 몇 개를 저장해야 하는지를 아직은 모르니 일단 $A$개라고 하자. 이후 $v_4$에서 인접한 정점들을 보면서, 인접한 정점들을 모두 $v_3$ 후보로 보고 가능한 $1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4$ 경로 중 $(v_2, v_3)$ 후보를 몇 개만 남겨둘 것이다. 마찬가지로 $(v_6, v_7 )$ 후보도 같은 방식으로 남겨둔 다음에, 마지막으로 8개의 점 번호가 서로 다른 최단거리를 계산해 주면 된다.

결국 문제는 정확히 어떤 정보를 계산해 줘야 할 지를 명확히 하는 것이다. 이 부분이 이 문제에서 가장 까다로운 부분이라고 할 수 있다.

먼저 $v_3$ 입장에서는 몇 개의 $v_2$를 후보로 관리해야 할까? $v_3$이 $v_5, v_6, v_7$과 겹치지 않는다는 가정 하에, $v_2$도 이들, 그리고 추가로 $v_4$와 겹치지 않으면 되므로 총 5개의 상위 후보를 관리하면 충분하다.

다음으로 $v_4$ 입장에서 최적해들을 관리할 떄에는 어떻게 해야 할까? 이 부분이 가장 어렵다. 일단 $v_4$와 인접한 $v_3$들은 각각 최대 $4$개의 후보를 가지고 있고, 이 개수의 합은 모든 $v_4$에 대해 최대 $4M$이므로 $O(M)$ 정도에 구할 수 있으면 충분하다. 이 정보들 중 가장 거리가 짧은 최적해 16개를 고르되, $v_2$가 같은 것은 최대 4개만 뽑고, 마찬가지로 $v_3$가 같은 것도 최대 4개만 뽑자. 이렇게 하면 어느 경우에도 $v_5$, $v_6$, $v_7$이 들어가지 않은 최적해가 이 16개의 해 안에 포함됨을 보일 수 있다. 16에서 더 수를 줄일 수도 있어 보이는데 그렇게 하진 않았다.

 

결론적으로 문제를 $O(N+M)$에 해결할 수 있다.