13317번 - 한 번 남았다
50 49
1 2 -1
2 3 -1
.
-> 틀린 제출
49 48 -1
48 47 -1
-> 맞는 제출
많은 분들이 앞선 제출을 하시고 틀린 다음 고치시는데,
저도 틀렸고 이유를 알고나서 봐도 인터넷에 제대로 설명되어있는 곳이 없어 남깁니다.
밸만 포드 알고리즘이
모든 간선을 update시도를 v번(사이클 체크 포함) 하는 것인데,
이번 문제는 지구이를 혼내주기 위해 v-1번째에 사이클이 아닌 update가 일어나게 setting하는게 목적이죠.
그래서 저랑 똑같이 틀리신 분들은
간선을 일직선으로 구성하면 되겠다 라고 생각하셨을 거에요.
but, 밸만포드의 작동 방식을 생각해보시면,
v-1번, 모든 간선을 통해 최단 거리를 update하죠
그래서 보통 s,e,w (시작, 도착, 가중치 )를 struct화하여 담아두었다가 전체를 모두 for문으로 도는 방식으로 구현하는데
이 때문에 첫 제출은 틀리게되는 겁니다.
작은 수가 중요한게 아니라 간선들이 바로바로 연결되게 setting한 것이 문제이죠
(50 49 / 49 48 / 48 47 이렇게도 안 되겠죠)
1 2 / 2 3 / 3 4 / 4 5 이런 식이면 모든 정점의 최단 거리가 1번만의 update 안에 이루어지는 것입니다.
이러면 지구이도 음수사이클이라고 안하겠죠.
반면 올바른 제출을 보고 잘 생각해보면, 아까 케이스보다 서서히 update되는 걸 느끼실 수 있어요.
그렇게 되면 v-1 번째에 사이클 없이 update를 하며
지구이를 완벽하게 논리로 압살! 할 수 있겠죠.
궁금하신 분들이 많을 까봐 적어봤어요. 감사합니다 :)
아래는 거꾸로가 아니라, 최단거리가 퍼져나가는 속도가 틀린 거라는 걸 보여주는 예시입니다.
댓글을 작성하려면 로그인해야 합니다.
dolchaelatte 1년 전 5
50 49
1 2 -1
2 3 -1
.
-> 틀린 제출
50 49
49 48 -1
48 47 -1
.
-> 맞는 제출
많은 분들이 앞선 제출을 하시고 틀린 다음 고치시는데,
저도 틀렸고 이유를 알고나서 봐도 인터넷에 제대로 설명되어있는 곳이 없어 남깁니다.
밸만 포드 알고리즘이
모든 간선을 update시도를 v번(사이클 체크 포함) 하는 것인데,
이번 문제는 지구이를 혼내주기 위해 v-1번째에 사이클이 아닌 update가 일어나게 setting하는게 목적이죠.
그래서 저랑 똑같이 틀리신 분들은
간선을 일직선으로 구성하면 되겠다 라고 생각하셨을 거에요.
but, 밸만포드의 작동 방식을 생각해보시면,
v-1번, 모든 간선을 통해 최단 거리를 update하죠
그래서 보통 s,e,w (시작, 도착, 가중치 )를 struct화하여 담아두었다가 전체를 모두 for문으로 도는 방식으로 구현하는데
이 때문에 첫 제출은 틀리게되는 겁니다.
작은 수가 중요한게 아니라 간선들이 바로바로 연결되게 setting한 것이 문제이죠
(50 49 / 49 48 / 48 47 이렇게도 안 되겠죠)
1 2 / 2 3 / 3 4 / 4 5 이런 식이면 모든 정점의 최단 거리가 1번만의 update 안에 이루어지는 것입니다.
이러면 지구이도 음수사이클이라고 안하겠죠.
반면 올바른 제출을 보고 잘 생각해보면, 아까 케이스보다 서서히 update되는 걸 느끼실 수 있어요.
그렇게 되면 v-1 번째에 사이클 없이 update를 하며
지구이를 완벽하게 논리로 압살! 할 수 있겠죠.
궁금하신 분들이 많을 까봐 적어봤어요. 감사합니다 :)
아래는 거꾸로가 아니라, 최단거리가 퍼져나가는 속도가 틀린 거라는 걸 보여주는 예시입니다.