14938번 - 서강그라운드
DFS 로 풀 수 있겠지 하면서 풀었습니다..
1시간 동안 9%에서 맞왜틀 외치던 저에게 깨달음을 준 반례입니다,,
A -> C -> D 로 가는 것이 최단일 때,
A -> B -> C 로 탐색하면서 C를 visited 처리해서 D에 도달 못할 수도 있단 것을 알게 됐네요.
최단거리 재야할 때는 BFS 쓰거나 다익스트라/플로이드 쓰는걸로
반례
5 15 52 4 5 20 31 2 62 3 73 4 91 3 21 5 14
---
정답 : 34
댓글을 작성하려면 로그인해야 합니다.
ch6403 2년 전 7
DFS 로 풀 수 있겠지 하면서 풀었습니다..
1시간 동안 9%에서 맞왜틀 외치던 저에게 깨달음을 준 반례입니다,,
A -> C -> D 로 가는 것이 최단일 때,
A -> B -> C 로 탐색하면서 C를 visited 처리해서 D에 도달 못할 수도 있단 것을 알게 됐네요.
최단거리 재야할 때는 BFS 쓰거나 다익스트라/플로이드 쓰는걸로
반례
5 15 5
2 4 5 20 3
1 2 6
2 3 7
3 4 9
1 3 2
1 5 14
---
정답 : 34