[최단거리] 골목길 문제에 대한 고찰, python

🤔 어느 부분을 신경쓰지 못했을까?

먼저 문제 링크
https://www.acmicpc.net/problem/1738

또 내가 작성한 답안 링크이다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_1738.py

간단한 문제라고 생각을 했다, 당연히 최장거리를 구하는 문제일리는 없으니까 간선에 -를 붙여서 넣어주는 것, 또 싸이클이 생기면 답이 될 수 없겠다고 당연하게 생각했다. 벨만포드 알고리즘을 쓰면 사이클을 확인하는 것은 쉬운 것이라 생각했다. (원리는 벨만포드에서 값이 갱신되는 최대 횟수는 모든 노드의 개수 -1 번 만큼만 가능하다. - 두 노드 사이에 최대 올 수 있는 간선의 개수가 V-1개가 최소이기 때문에 하지만, 만약 V번의 순회동안 마지막 V번째 순회에서도 최솟값이 갱신된다면 이것은 사이클이 존재한다.)

실제로도 맞는 풀이 방법이었지만 어려운 문제 답게 함정이 존재했다. 그것 때문에 거의 2시간은 고민해본 것 같다.
하지만 결국 떠올리지 못하여 다른 사람들의 풀이를 참고하였다.

사이클이 있다고 해서 도착 점에 가지 못 하는 것은 아니다.

이게 핵심이었다. 출발지 1과 N 사이에 사이클이 없고 가는 경로 도중에 사이클이 있는 경우를 확인하지 않았기 때문에 계속해서 틀리게 된 것이다. 이를 위해서 역순으로 bfs를 시도해 N에서 1로 오는 길이 있는지 찾음으로 해결했다.

역순 bfs + 벨만 포드를 사용해야 했던 문제이다.

아직 최단 거리에 대한 확실한 개념이 잡히지 않은 것 같아 넘나리 슬펏다리ㅠ