lobwidu   2년 전

아래와 같이 풀이 접근 방법으로 했는데

33%에서 계속 틀린다고 뜨네요..

애드혹 스타일의 아이디어를 요구하는 간단한 다익스트라 문제라 생각했는데,,

변수 초기화 문제 인지..  

혹시 어느 부분이 잘 못 되었는지 도움 주실 분 계실까요?

pom0319   2년 전

목적지로 가는 최단경로가 특정 경로를 포함하는 경로와 포함하지 않는 경로 모두가 있을 수 있습니다. 간단한 예시를 들자면 a에서 d로 가는 최단경로를 알고 싶은데, <a, b>, <b, d>, <a, c>, <c, d> 이렇게 4개의  edge가 모두 가중치 1로 존재한다고 해봅시다. 이때 특정 경로 <a, c>를 지나는지를 알고 싶은데, 다익스트라 알고리즘에 의해 선택된 경로가 a -> b -> d라면, 경로의 길이가 같은 a -> c -> d가 있음에도 불구하고 최단경로로 간다면 <a, c>를 지나갈 수 없다는 결과가 나오게 될 겁니다. 작성하신 알고리즘에선 특정 경로의 길이를 일반 경로보다 더 길다고 설정하셨기 때문에 최단경로가 여러개일 경우 항상 특정 경로를 포함하는 최단 경로는 존재하지 않는다는 결과를 낳게 될 것입니다.

lobwidu   2년 전

감사합니다.

최단경로가 여러개일 때에 대한 생각을 못했네요..

특정 경로에 대한 가중치를 cost * 2 - 1 로 하여 일반 경로 가중치 (cost * 2) 보다 짧게 설정하였습니다.

또한,

dist 배열을 초기화 하는 MAX_VAL 값도 단순히 Integer.MAX_VALUE를 하게 되면 홀수(2147483647)가 들어가게 되어

Integer.MAX_VALUE / 2 * 2 하여 짝수로 변경(2147483646)하도록 수정하니 통과하였습니다.


어제 이 문제만 3시간을 들여다 봤는데 ㅠㅠ pom0319님, 다시 한 번 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.