'2024/02 글 목록

처음 풀어보는 백준의 플래티넘 문제. 내가 풀었던 방식 부터 적을 생각이다. 우선 문제는 이름 그대로 최단 경로가 아닌 거의 최단 경로를 찾는다. 그래프에서 최단경로들의 간선을 제외한 그다음에 나오는 최단경로를 찾는 문제 우선 생각했던 방법은 다익스트라로 간선들을 지우면서 나간뒤 다익스트라를 한번더 돌릴예정이였다. 그렇게 테스트 하였지만 결과는 8% 실패 실패 이유는 다익스트라로 간선을 지울경우 간선이 하나만 지워지는 문제가 생긴다. 위 의경우 최단경로는 두개로 1 2 4 5 와 1 3 4 5가 있다. 거의 최단경로는 저두개를 제외한 1 ->5인 이여야 하지만 경로를 먼저 지워주게 될경우 4->5가 공유되지않으면서 거의최단경로는 6이 나오게된다. 정상적인경우 위처럼 최단경로들을 제외하여 4->5로가는 길..

알고리즘 2024. 2. 13. 16:49

이전 1 다음