10282번 - 해킹
시작하기 전에 반례를 찾아오신 분들은 다른 분들꺼 참고해보시면 도움이 될겁니다!
저는 이번 문제를 다익스트라로 풀어야 하는 전형적인 문제입니다.
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를 제외한 나머지 값 중 큰 값을 가져오면 되는 것입니다.-> 갱신을 통해 모든 노드에 대한 최선의 시간이 계산되어 있기 때문입니다.
도움이 되시길 바라며..
댓글을 작성하려면 로그인해야 합니다.
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를 제외한 나머지 값 중 큰 값을 가져오면 되는 것입니다.
-> 갱신을 통해 모든 노드에 대한 최선의 시간이 계산되어 있기 때문입니다.
도움이 되시길 바라며..