1504번 - 특정한 최단 경로
시작점을 s, 끝점을 e, 중간에 들러야 하는 두 지점을 v1 과 v2 라고 하겠습니다.
전 처음에 이 문제를 풀 때 경우의 수가 엄청 많은 것 같아서 살짝 의아했습니다.
단순히 s - v1 - v2 - e / s - v2 - v1 - e 이런 방식 말고
s - e -v1 - e - v2 - e 이런 식으로 진행하는 방식이 더 적은 거리 값이 나올 수도 있었기에 이런 경우는 어떻게 계산해야 해나 싶었습니다.
하지만 결국 다시 생각해보면 s - e -v1 - e - v2 - e 루트는 다음과 같이 볼 수 있었습니다.
s - (e -v1) - (e - v2) - e = s - v1 - v2 - e
결국 복잡해 보이는 방식이지만 시작점인 s 에서 v1 으로 가는 길 중간에 끝점인 e가 들어가 있을 뿐, 결국 저희가 코드를 돌리게 되면 s 에서 e를 거쳐 v1으로 가는 것이 s에서 v1으로 가는 최솟값인 셈이었습니다.
v1으로 가는 길 중간에 v2를 만약 거쳐가게 된다면 s - v1 - e 이런 식으로 가면 되지 않나? 싶지만 결국 해당 루트도 쪼개보면
s - v1 - e = s - (v2 - v1) - e 이런 식으로 쪼개지게 됩니다.
s - v1 - v2 - v1 - e 같은 방식도 결국엔 s 에서 v2로 가는데 v1이 끼어있을 뿐이니 s - v2 - v1 - e 로 볼 수 있습니다.
결국 저희가 확인해야 할 경우는 s - v1 - v2 - e 와 s - v2 - v1 - e 이 두 가지 경우 뿐이라고 볼 수 있을 것 같습니다.
생각을 정리하고 싶어서 작성했는데 혹시 이상한 부분이 있다면 조언 부탁드리겠습니다.
댓글을 작성하려면 로그인해야 합니다.
scottku 2년 전 14
시작점을 s, 끝점을 e, 중간에 들러야 하는 두 지점을 v1 과 v2 라고 하겠습니다.
전 처음에 이 문제를 풀 때 경우의 수가 엄청 많은 것 같아서 살짝 의아했습니다.
단순히 s - v1 - v2 - e / s - v2 - v1 - e 이런 방식 말고
s - e -v1 - e - v2 - e 이런 식으로 진행하는 방식이 더 적은 거리 값이 나올 수도 있었기에 이런 경우는 어떻게 계산해야 해나 싶었습니다.
하지만 결국 다시 생각해보면 s - e -v1 - e - v2 - e 루트는 다음과 같이 볼 수 있었습니다.
s - (e -v1) - (e - v2) - e = s - v1 - v2 - e
결국 복잡해 보이는 방식이지만 시작점인 s 에서 v1 으로 가는 길 중간에 끝점인 e가 들어가 있을 뿐, 결국 저희가 코드를 돌리게 되면 s 에서 e를 거쳐 v1으로 가는 것이 s에서 v1으로 가는 최솟값인 셈이었습니다.
v1으로 가는 길 중간에 v2를 만약 거쳐가게 된다면 s - v1 - e 이런 식으로 가면 되지 않나? 싶지만 결국 해당 루트도 쪼개보면
s - v1 - e = s - (v2 - v1) - e 이런 식으로 쪼개지게 됩니다.
s - v1 - v2 - v1 - e 같은 방식도 결국엔 s 에서 v2로 가는데 v1이 끼어있을 뿐이니 s - v2 - v1 - e 로 볼 수 있습니다.
결국 저희가 확인해야 할 경우는 s - v1 - v2 - e 와 s - v2 - v1 - e 이 두 가지 경우 뿐이라고 볼 수 있을 것 같습니다.
생각을 정리하고 싶어서 작성했는데 혹시 이상한 부분이 있다면 조언 부탁드리겠습니다.