qkqktl5310   2년 전

시작하기 전에 반례를 찾아오신 분들은 다른 분들꺼 참고해보시면 도움이 될겁니다!

저는 이번 문제를 다익스트라로 풀어야 하는 전형적인 문제입니다.


1. 다익스트라는 항상 최선의 값을 선택해가며 값을 갱신해 가야합니다. (우선순위 큐)

2. 총 걸린 시간을 찾는 방법

아래 예제를 보겠습니다!

1

4 5 1

4 1 1

2 4 10

3 1 2

2 3 2

3 2 2

answer 4 4

그림을 그려서 직접 확인해보시면 1에서 4까지 모든 노드를 방문했을때 4초가 지나면 모든 노드를 방문했다는 것을 알 수 있습니다.

결국 핵심은 시간을 담아놓은 배열에서 Integer.MAX_VALUE를 제외한 나머지 값 중 큰 값을 가져오면 되는 것입니다.
-> 갱신을 통해 모든 노드에 대한 최선의 시간이 계산되어 있기 때문입니다.

도움이 되시길 바라며..

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