13418번 - 학교 탐방하기
1. 간선에 방향이 없다.
오르막 내리막은 분명히 방향이 있을텐데 이 문제는 없다고 해 놨습니다.
현실과 맞지 않으므로 이해가 잘 안 되죠.
오르막 => 험한 길
내리막 => 쉬운 길
이렇게 놓고 보면 문제 이해가 한결 쉬울겁니다.
2. 오르막길과 내리막길 가중치가 반대다.
보통 비용이 많으면 숫자가 높고 적으면 낮죠.
근데 이 문제는 오르막길(비용이 많음)이 0이고 내리막길(비용적음)이 1입니다.
그 반대예요.
이상 두 가지 빠지기 쉬운 함정이었습니다.
+추가)
0번노드와 (0,1) 간선이 특별한 노드와 간선인것처럼 따로 구성해 놓았는데 어차피 연결해야할 노드및 간선이므로 특별취급하지 않아도 됩니다.
맞아요 오르막 내리막 비유가 별로였던 것 같습니다.. 직관적으로 생각해봤을 땐 방향 그래프로 구현하는게 맞는데 실제 문제는 무방향 그래프여서 좀 벙쪘네요..
댓글을 작성하려면 로그인해야 합니다.
codebabo 3년 전 6
1. 간선에 방향이 없다.
오르막 내리막은 분명히 방향이 있을텐데 이 문제는 없다고 해 놨습니다.
현실과 맞지 않으므로 이해가 잘 안 되죠.
오르막 => 험한 길
내리막 => 쉬운 길
이렇게 놓고 보면 문제 이해가 한결 쉬울겁니다.
2. 오르막길과 내리막길 가중치가 반대다.
보통 비용이 많으면 숫자가 높고 적으면 낮죠.
근데 이 문제는 오르막길(비용이 많음)이 0이고 내리막길(비용적음)이 1입니다.
그 반대예요.
이상 두 가지 빠지기 쉬운 함정이었습니다.
+추가)
0번노드와 (0,1) 간선이 특별한 노드와 간선인것처럼 따로 구성해 놓았는데 어차피 연결해야할 노드및 간선이므로 특별취급하지 않아도 됩니다.