https://www.acmicpc.net/problem/24888
문제요약
- 1번 -> N번 정점까지 최단 경로로만 이동함
- 노트조각을 모두 주으면서 1번 -> N번 최단거리(N, M = 20만, 가중치 10^9)
- 최단거리 경로 출력
접근법
- 문제를 잘 이해해야함
- 어떻게 이동하든 1 -> N은 최단거리로 이동하는 것임. 이 상태에서 모든 노트조각을 주을 수 있는가? 문제임
- 노트조각을 줍는 경로의 최단거리는 TSP 문제임
- 일단 최단거리를 구함 : dijkstra
- 1번점부터 각각의 점에 도달하는 최단거리를 구할 수 있음
- 노트가 있는 점의 최단거리도 구할 수 있음 => dijkstra에서 최단거리부터 나타날 것이므로 모으면 노트가 있는 점들을 정렬한 효과가 됨. 이때 빠진점이 있는지 체크함
- A -> B점을 갈 수 있는지 판단함 : 1 -> 다음 노트, 다음 노트 -> 다다음 노트, .... , 마지막 노트 -> n
- DFS 비슷하게 판단함
- dfs(시작, 끝, 현재)
- 현재에서 갈 수 있는 점을 확인하는데 이때 이동거리 = dijkstra로 구한 거리 여야 탐색을 진행함
- 이렇게해서 끝까지 왔으면, 그 동안의 경로를 저장함
- 끝 지점의 거리를 벗어나는 구간은 탐색 안함
- 이런 식으로 모든 구간에 대해 탐색을 해봄
- DFS가 무한히 돌아가지는 않음 왜냐면 최단거리가 되는 지점만 이동 + 특정 구간에서만 탐색을 진행하기 때문임. 혹시라도 끝까지 가더라도 찾을만한 이유가 있어서 찾거나, 못찾으면 더 이상 진행을 안하니까 괜찮음
공식해설 + 다른 생각
- 공식해설 : dijkstra로 그래프를 구해놓고, 여기서 DP 적용 => 가능한 많은 "노트 노드"를 가져간다는 생각으로 접근
- dijkstra로 역방향 그래프를 생성한 후, n번 노드에서 "노트 노드"가 많은쪽으로 이동하고 싶었는데 생각해보니 결과적으로 DP 모습이었음
newbieski