codebabo   3년 전

1. 간선에 방향이 없다.

오르막 내리막은 분명히 방향이 있을텐데 이 문제는 없다고 해 놨습니다.

현실과 맞지 않으므로 이해가 잘 안 되죠.

오르막 => 험한 길

내리막 => 쉬운 길

이렇게 놓고 보면 문제 이해가 한결 쉬울겁니다.

2. 오르막길과 내리막길 가중치가 반대다.

보통 비용이 많으면 숫자가 높고 적으면 낮죠.

근데 이 문제는 오르막길(비용이 많음)이 0이고 내리막길(비용적음)이 1입니다.

그 반대예요.

이상 두 가지 빠지기 쉬운 함정이었습니다.

+추가)

0번노드와 (0,1) 간선이 특별한 노드와 간선인것처럼 따로 구성해 놓았는데 어차피 연결해야할 노드및 간선이므로 특별취급하지 않아도 됩니다.

pjhisgod   3년 전

맞아요 오르막 내리막 비유가 별로였던 것 같습니다.. 직관적으로 생각해봤을 땐 방향 그래프로 구현하는게 맞는데 실제 문제는 무방향 그래프여서 좀 벙쪘네요..

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