leaps   2년 전

저는 항상 알고리즘을 접근할 때 제 직관으로 먼저 접근을 합니다.

그래서 직관적으로 결국 시작지점에서 부터 시작하여 현재 갈 수 있는 간선만 우선순위큐에 넣고 시작하면, 최대 V-1번만 Dequeue하면 문제를 풀 수 있다고 생각하였습니다.

그래서 제가 생각한 로직은 다음과 같습니다.

  1. src에서 갈 수 있는 간선을 코스트 계산해서 우선순위 큐에 넣는다.
  2. 우선순위 큐에서 하나를 pop, 그 후 만약 dist[cur.obj] != INF ( 아직 최소값이 결정되지 않은 버텍스 )라면 그 버텍스의 최소값을 수정하고 인접한 간선을 모두 우선순위 큐에 넣는다.
  3. 이 과정을 V-1번 반복

이렇게 해결하였습니다. 

그런데 일반적으로 코드구현을 이런식으로 하지 않더군요.

제가 본 일반적인 코드의 루틴은 다음과 같습니다.

  1. Src만 dist를 0으로 설정하고 나머지는 INF로 설정한 뒤 우선순위 큐에 담는다. ( 버텍스 번호와 Cost를 담음 )
  2. pop된 cost와 dist[vertex]를 비교하여 dist[vertex]가 cost보다 같거나 크면 진행, 아니면 Continue
  3. 모든 간선을 확인하여 dist[vertex]보다 작은 cost로 이동할 수 있다면 Q에 삽입한다.

입니다.

제가 궁금한 점은 우선 1번, 왜 src vertex와 Cost만 큐에 넣으면 될 것인데 왜 나머지 버텍스를 INF Cost와 함께 삽입하는지가 이해가 안됩니다. 

그리고 2번, 이 구조는 BFS로 다익스트라를 접근한 케이스라 무조건 cost가 최소인 간선을 얻게 될 것인데, 왜 굳이 저런 조건문이 추가된건지 궁금합니다. 그냥 제 방식대로 dist[cur.obj] != INF로 해도 될 거 같은데요;


이런 질문을 드리는 이유는 보편적인 코드에는 이유가 있기 때문입니다.

다익스트라는 유명한 알고리즘이고, 저보다 앞서 더 많이 생각한 사람이 생각해서 짠 코드인데, 이유가 있을 것이라고 생각합니다.


djm03178   2년 전

"왜 다른 버텍스까지 추가하는가"

여러 사람들의 다익스트라 코드를 보아왔지만 INF인 정점까지 처음에 다 우선순위 큐에 넣는 경우는 오히려 거의 보지 못한 것 같습니다. 배울 때는 그렇게 배우긴 했었는데, 그건 STL의 priority_queue가 아니라 중간의 값의 변경이 가능한 형태의 힙을 사용한 거라 std::priority_queue에서는 무의미해 보입니다.

"왜 굳이 dst가 cost와 다르다는 것을 체크해야 하는가"

그렇게 하지 않으면 어떤 정점이 우선순위 큐에 여러 번 들어갔다 나올 때, 처음에 나왔을 때의 cost만 가지고 계산을 해야 하는데 그보다 이전에 들어간, 더 나쁜 cost 상태에서 또 연산을 할 수 있기 때문입니다. 질문자님의 경우 무조건 간선을 큐에 다 넣은 뒤에, 큐에서 빼냈을 때 그 끝점의 거리를 갱신해주기 때문에 INF가 아닌지만 체크하면 되지만, 후자의 코드의 경우 큐에 삽입할 것인가 여부 자체를 dst 배열을 통해 미리 판단하기 때문에 (이는 평균적으로 힙에 들어갈 원소의 수를 줄여주는 역할을 합니다) 이와 같은 체크가 반드시 필요합니다.

djm03178   2년 전

물론 이걸 굳이 체크하지 않아도 답을 구하는 데에 문제는 없겠고 큐에 중복 삽입되지도 않겠지만, 34~39번째 줄을 불필요하게 반복하는 일이 벌어지게 됩니다.

leaps   2년 전

좋은 답변 감사합니다!

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