K번째 최단경로를 구하는 문제인데 같은 경로가 여러개 중첩될 때 전부다 센다는 점이 매우 이상합니다.
구하는 과정에서야 K번째로 다익스트라에서 방문하게 되는 경로 정도로 이해할 수 있지만, 사실 경로들이 들어있는 집합에서 K번째를 찾는다고 생각하면 경로의 길이 순으로 정렬해야 할 텐데 길이가 같은 경로끼리는 서로 비교가 불가능하기 때문에 K번째 최단 경로에서 '번째' 부분이 잘 정의되지 않습니다. 즉, 그냥 문제 오류입니다.
경로끼리 들어있는 벡터를 sort한다고 생각하면 되지 않냐고 생각할 수도 있는데, 그렇다해도 K번째에 올 수 있는 경로는 여러개 입니다. 당연히 길이는 같겠지만 문제 설명에서는 K번째 최단 경로가 있고, 그 소요 시간을 출력하라는 식으로 설명되어 있습니다. K번째 최단 경로가 잘 정의되어 있어야 그러한 말이 가능한데 애초에 그게 잘 정의되지 않습니다..
단순히 문장을 바꿔서 설명을 매끄럽게 할 방법이 없는 것도 사실입니다. 문제 제목을 K번째 최단 경로라고 설정한 순간부터 문제가 잘못된 터라 더 그렇습니다. 제일 좋은 방법은 문제 예시에서
3 3 2
1 2 1
2 3 1
1 3 2
와 같은 예시를 추가하고,
이 경우 3번 정점으로 가는 경로들의 길이를 나열하면 [2, 2] 이므로 2번째 값이 2이므로 답이 2가 된다.
정도의 설명을 덧붙이는게 최선이라고 생각합니다. 물론 이마저도 올바른 설명이 아니긴 합니다만, 적어도 헷갈려서 잘못 풀진 않을 것 같습니다.
tkfkddl59323 3년 전 1
K번째 최단경로를 구하는 문제인데 같은 경로가 여러개 중첩될 때 전부다 센다는 점이 매우 이상합니다.
구하는 과정에서야 K번째로 다익스트라에서 방문하게 되는 경로 정도로 이해할 수 있지만, 사실 경로들이 들어있는 집합에서 K번째를 찾는다고 생각하면 경로의 길이 순으로 정렬해야 할 텐데 길이가 같은 경로끼리는 서로 비교가 불가능하기 때문에 K번째 최단 경로에서 '번째' 부분이 잘 정의되지 않습니다. 즉, 그냥 문제 오류입니다.
경로끼리 들어있는 벡터를 sort한다고 생각하면 되지 않냐고 생각할 수도 있는데, 그렇다해도 K번째에 올 수 있는 경로는 여러개 입니다. 당연히 길이는 같겠지만 문제 설명에서는 K번째 최단 경로가 있고, 그 소요 시간을 출력하라는 식으로 설명되어 있습니다. K번째 최단 경로가 잘 정의되어 있어야 그러한 말이 가능한데 애초에 그게 잘 정의되지 않습니다..
단순히 문장을 바꿔서 설명을 매끄럽게 할 방법이 없는 것도 사실입니다. 문제 제목을 K번째 최단 경로라고 설정한 순간부터 문제가 잘못된 터라 더 그렇습니다. 제일 좋은 방법은 문제 예시에서
3 3 2
1 2 1
2 3 1
1 3 2
와 같은 예시를 추가하고,
이 경우 3번 정점으로 가는 경로들의 길이를 나열하면 [2, 2] 이므로 2번째 값이 2이므로 답이 2가 된다.
정도의 설명을 덧붙이는게 최선이라고 생각합니다. 물론 이마저도 올바른 설명이 아니긴 합니다만, 적어도 헷갈려서 잘못 풀진 않을 것 같습니다.