정보를 잘 저장해서 사전순 다익스트라 문제를 풀어봅시다.

 얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다.

 

---

 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요?

 

 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요.

 

 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 한다고 했어요. 여기서 중요한 정보는 사전순하고, 특정 위치에서 e까지 가는 데 거리입니다. 양방향이니, 간선들의 방향을 뒤집고 할 필요 없이, e를 시작점으로 해서 다익스트라를 한 번 돌립니다. 

 

 

 e가 4이니, 4를 시작점으로 해서 다익스트라를 돌립시다.

 

 

 그러면 최단 거리는 위와 같이 구해집니다. 여기서 4는 최단 거리가 0이므로 표시를 하지 않았습니다. 그리고, 1은 거리가 6, 2는 거리가 2, 3은 거리가 3이므로, 지점 1 밑에 (6)으로, 2 밑에는 (2)로, 3 밑에는 (3)으로 표시해 두었습니다. 이제 답에 대한 탐색을 할 것인데, 어떻게 하면 좋을까요?

 

 구현하기 편한 방법은, 각 지점마다 연결 정보들을 목적지 오름차순으로 정렬하는 것입니다. 전처리 해야 하는 작업입니다.

 

 

 이렇게요. 그러면, 답이 될 수 있는 후보해가 나타나면 바로 break를 걸어서 빠져나올 수 있습니다.

 

---

 이제, 알고리즘을 돌려봅시다.

 

 현재 알려진 경로는 [1]입니다. 누적 경로 길이는 0입니다. 제가 1에서 2로 갔을 때 최단 거리로 갈 수 있을까요? 이걸 보려면, 1에서 2로 가는 경로에다가, 2에서부터 4로 가는 최단 경로를 봐야 합니다. 1에서 2로 가는 경로의 길이는 4입니다. 그리고, 2에서부터 4까지 가는 최단 경로의 길이는 2입니다. 4 + 2 = 6인데, 6은 1에서부터 4까지 가는 최단 경로와 같습니다. 따라서, 1에서 2로 가야 합니다.

 

 

 다음에 2에서 어디로 가야할 지를 골라야 합니다. 먼저 1부터 봅시다. 빨간 색은 이미 제가 선택한 경로에요. 그 길이는 4입니다. 여기서 1로 가게 되면, 2에서 1로 가는 거리 4에다가, 1에서부터 4까지 가는 최단 경로의 길이 6을 더한 값만큼 경로 길이가 될 겁니다. 4 + 4 + 6 = 14인데요. 이는 1에서부터 4까지 가는 최단 거리인 6보다 큰 상황입니다. 따라서, 이 경우는 제외됩니다.

 

 

 만약에, 바로 4로 간다면 어떨까요? 빨간색, 이미 선택한 경로들의 길이 합은 4입니다. 그리고, 2에서 4까지 가는 경로의 길이는 2입니다. 그리고 4에서부터 4까지의 최단 거리는 0입니다. 4 + 2 = 6이네요. 따라서 조건을 만족하므로, 4를 선택합니다.

 

 

 그래서, 최종적으로 선택하는 경로는 1 - 2 - 4가 됩니다. 다른 경로로 1 - 3 - 4도 있는데, 1 - 3 - 4는 1 - 2 - 4보다는 사전순으로 뒤에 있으므로 제외됩니다. 그리고 돌아올 때에는 (문제 의도상) S에서 E로 갈 때 거쳤던 지점을 방문하지 않는, 4에서 1까지의 최단 경로를 찍어야 합니다.

 

 dijkstra를 돌리는 함수를 2개 만들 수는 없으니, 어떻게 공통화를 시킬지 생각해 봅시다. 결국, 다익스트라던 bfs던 인접한 정점이면 검사해 보는 것은 동일해요. 여기서 검사 조건을 하나 더 추가시키면 어떨까요? 방문해야 하는 정점 to에 대해서 flag[to]가 참이 아니면 방문하면 어떨까요?

 

 flag는 s에서 e로 갈 때 중간에 어떤 노드를 방문했는지를 저장합니다. 만약에 to를 방문했다면 flag[to]가 1이 됩니다.

 

 

 40번째 줄을 보면, C.to와 인접 노드들을 탐색하는데, flag[to]가 1이면 continue를 해 버립니다. 인접한 노드가 이미 s에서 e로 갈 때 방문했다면, 탐색하지 않는데요. 처음에 s에서 e로 갈 때는 flag가 0으로 모두 채워져 있으니, 41번째 줄에는 걸리지 않습니다. 경로를 만들면서, 중간에 방문한 노드들이 flag값이 true가 세팅이 되면서 e에서 s로 갈 때 dijkstra를 한 번 더 호출할 것인데, 이 때 걸리는 겁니다.

 

 먼저, e를 시작점으로 해서 다익스트라를 한 번 돌려요. 이유는 임의의 경로 x에서 e까지 가는 최단 경로를 구해야 하기 때문입니다. 역 연산을 한 거라 생각하시면 됩니다.

 

 s에서 e로 갈 때 경로 추적 코드입니다. con[x]에는 x와 인접한 노드들이 인접한 노드 번호 오름차순으로 저장되어 있습니다. 그러므로, 계속 돌면서, 최단 거리로 갈 수 있는 후보해가 나오면 바로 break를 걸어버릴 수 있습니다.

 

 

 현재 s에서 cur까지 가는 경로를 알고 있을 때, cur_ans는 s에서 cur까지 가는 경로 길이의 총 합입니다. to는 cur와 인접한 노드입니다. cur에서 to까지 가는 경로 알고 있고, to에서 e까지 가는 최단 거리 min_dist[to]도 알고 있습니다. 이 3개의 값의 합이 s에서 e까지 가는 최단 경로의 합 ans와 같다면 break를 걸어버리면 됩니다.