5719

시작 https://lotuslee.tistory.com/137 본문을 참고하였습니다. 문제를 읽어보면 한가지 좋은 아이디어를 생각해볼 수 있었는데 구현이 쉽지 않았습니다. 아이디어는 비교적 간단합니다. 1. 다익스트라로 최단 경로를 구합니다. 2. 최단 경로들을 모두 제외 합니다. 3. 다익스트라로 다음 최단 경로를 구합니다. 그림으로 보면 다음과 같습니다. 각 순서는 그림에서 왼쪽부터 1, 2, 3으로 확인해 볼 수 있습니다. 소스코드를 우선 살펴보겠습니다. 코드 중에 preNodeCollections, ArrayList 를 선언해 두었습니다. 최소 비용을 가진 경로를 담아두기 위한 목적인데, 거리 값이 갱신 되면 왼쪽에 보이는 1번 경로가 clear 되고 2번 경로가 preNodeCollection..