문제 링크1854번: K번째 최단경로 찾기풀이가장 빠른 경로가 아니라, K번째 최단경로를 구해야 하는 문제이다. 일반적인 최단 경로야 다익스트라 등으로 구하면 그만이지만, 특정 번째의 최단경로의 값은 어떻게 구해야 할지 선뜻 떠오르지 않을 것이다.더군다나 이 문제는 최단 경로를 구할 때 같은 에지의 중복이 가능하며, 출발지와 도착지가 자기 자신인 에지도 존재한다! 즉, 이런 것도 가능하다는 뜻이다.다음 그래프에서 1번 노드에서 1번 노드의 1번째 최단 경로는 0이다. 그리고 2, 3번째 최단 경로는 각각 2, 4가 된다. 반면 2, 3번 노드로부터 1번 노드의 최단 경로는 -1이다. 2, 3번 노드에서 1번 노드로 가는 경로가 없기 때문이다.이렇게 경로 중복도 가능하고, 출발지와 도착지가 같은 에지도 존..

문제 링크1162번: 도로포장풀이최단 경로를 구하는 문제인데, 도로 K개를 포장해서 경로를 줄일 수 있다는 조건이 붙었다. 최단 경로를 구하기 위해서 어떤 도로를 포장해야 할까?1. 그리디하게 소요 시간이 긴 도로부터 포장하기소요 시간이 긴 도로를 줄여나가는 방식으로 최단 경로를 구하겠다는 관점은 나름 합리적이다. 하지만 그렇게 해서 포장하기 전보다 더 나은 최단 경로를 구할 수 있다고 보장할 순 없다. 기존의 최단 경로에서 도로를 포장해 나가야 의미가 있지, 최단 경로에 포함되지 않은 도로를 포장해 봤자 의미가 없다.2. 포장하는 모든 경우의 수를 구하고, 그때마다 일일이 다익스트라로 최단 경로 구하기쉽게 말해 완전탐색인데, 이건 그냥 봐도 시간 초과의 여지가 다분하다. 포장 도로의 개수가 최대 20개..