wony6731   4년 전

제가 다익스트라 알고리즘 c++ 소스코드를 보고 제가 짜는 스타일에 맞게 코드를 변형하며 짰습니다.

여기서 대부분 같으나 비용이 최소인 곳을 방문하기 위한 우선순위 큐를 저는

저렇게 우선순위 큐를 구현해 사용하기 때문에 바꾸어 주었습니다.

우선순위 큐말고는 크게 다르지 않아 저 부분에서 시간초과가 나는 것이라고 추측하고 있는데...

맞는건가요? ㅜ 아니라면 왜 시간초과가 발생하는 것일까요...

제가 참고한 소스코드 링크는 여기입니다.

---------------------------------------------------------------

+ 코드를 살펴보다 또 의심되는 부분이 생겼는데 구조체를 선언해줘서 큐에 삽입하는 것과 pair를 사용하는 것도 시간초과에 영향을 미칠 수 있었을까요??? 참고한 코드는 pair를 사용하여 삽입하고 정렬해주어서 든 생각입니다 ㅜㅜ

clrmt   4년 전

일단 operator의 부호가 반대입니다:

bool operator < (Node a, Node b){

  return a.cost > b.cost;

}

원본 소스를 잘 보시면 기본값의 pair 비교를 쓰기 위해 cost 값을 마이너스해서 넣는 것을 확인할 수 있습니다. 그러면 마이너스 중에서 큰 값을 찾기 때문에 절댓값이 가장 작은 것을 고릅니다.

그리고 이 코드에서는 시작점이 부여되지 않았습니다.(제가 이것때문에 엄청 헤맸습니다.)

pair는 첫 번째 값 기준으로, 같다면 두 번째 값을 기준으로 정렬하므로 클래스를 새로 만들어 cost만 정렬해주는 쪽이 이론적으로는 더 빠를겁니다.

clrmt   4년 전

시간 초과가 나는 것은 우선순위 큐가 가장 큰 값을 먼저 뽑아냈기 때문입니다. 특히나 62번째 줄에서 부등호가 >로 되어있어서, 기존의 최단거리와 같은 값이라면 우선순위 큐에 계속해서 추가될 수 있습니다. 일단 operator의 부호를 바꾸고, 시작점에 관한 두 줄을 고친 뒤에 제출을 해 보시고, 62번째 줄을 >=로 고치고 나서 제출해 결과를 비교해 보세요.

댓글을 작성하려면 로그인해야 합니다.