22865번 - 가장 먼 곳
TLE가 나오는 케이스입니다
input.txt
홀수번째 장소들은 각자 이웃한 홀수번째 장소 2개와(홀수 - 2, 홀수 + 2) 10000의 길이로 연결되어 있고,
짝수번째 장소들은 이웃한 홀수번째 장소 2개와(짝수 - 1, 짝수 + 1) 1의 길이로 연결되어 있습니다.
1번 장소에서 출발한다고 가정하면
진행횟수 | 큐 내의 원소
0 | {1}
1 | {3, 2}
2 | {5, 4, 3}
...
과 같이 되는데, 2번재 진행시 주가된 3이, 1번째 진행시 이미 존재한 3의 경로와 똑같이 따라가며, 한번 더 처리되게 됩니다.
저런 원소들이 반복적으로 쌓여, 최악의 경우 (N^2)번 연산하게 됩니다
댓글을 작성하려면 로그인해야 합니다.
lhs456852 1년 전 0
다익스트라 알고리즘을 이용하여 풀어야 하지만 아래 코드처럼 bfs를 변형시킨 것으로 풀었을 때도 여유롭게 통과가 되었습니다.
아래와 같은 방식의 경우에는 시간초과가 나는 반례가 있을 것이라고 생각하는데 혹시 알려주실 수 있으신가요?
찾아 보고자 했지만 찾지 못했습니다.