간선의 가중치가 곧 거리를 나타내는 것이니 최단 경로라고 해도 문제될 것이 없습니다.
1753번 - 최단경로
답변 감사드립니다.
제가 애를 먹었던 이유를 설명드리자면
제가 아직 많은 문제를 풀어보진 않았지만, 가중치 그래프 문제에서 가중치에 비용, 거리, 시간 등 거리 외의 값이 들어가는 경우를 적지 않게 봤습니다.
저희가 부산까지 갈때 비용이 적게 드는 경로와, 최단 경로는 다르듯 추가적인 설명이 있어야 할 것 같습니다.
제가 아직 "가중치"의 개념이 익숙하지 않아 실례를 범했다면 사과드리겠습니다.
https://en.wikipedia.org/wiki/...를 참고하면,
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
정의가 처음부터 가중치 합을 최소로 하는 경로를 찾는 문제입니다. 원래 문제가 올바른 정의가 맞습니다.
아하! 제가 부족하게 알고 있었네요
알려주셔서 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
catbirdseat 3년 전
해당 문제에서 요구하는 출력은 "최단 경로"의 경로값이 아닌 "최소 경로값" 입니다.
예를 들어, 1에서 2까지 경로값이 100, 1에서 3까지 경로값이 1, 3에서 2까지 경로값이 2일 경우
1에서 2까지 가는 최단 경로는 1->2 이고 이 경우 경로값은 100이 돼야 합니다.
그러나 문제에서 요구하는 바는 최소 경로값 즉, 1->3->2 이며 이렇게 되면 답은 4입니다.
수정 부탁드립니다!