[다익스트라] BOJ#1753 -최단경로

[ye-yo]

⚠️ 나의 풀이

    while(!pq.empty()){
        int index = (pq.top()).first;
        pq.pop();
        visited[index] = 1;
        for(int j = 0; j< map[index].size(); j++){
            pair<int,int> next = map[index][j];
            int nextNode = next.first;
            if(visited[nextNode]) continue;
            int nextWeight = next.second;
            if(dist[nextNode] > dist[index] + nextWeight){
                dist[nextNode] = min(dist[nextNode], dist[index] + nextWeight);
                pq.push(next);
            }
        }
    }

❗️ 오답 원인 분석

• 다음 정점을 탐색할 때 업데이트 된 정점 정보를 넘겨줘야 함.

  pq.push({nextNode, cost + nextWeight});

• 비교할 비용 정보는
  다른 경로로 해당 정점까지 오는 비용(저장된 비용) vs 이전 정점거쳐 해당 정점까지 오는 비용 이므로
  비교해야 할 값은 아래의 값이 아니라

dist[nextNode] vs dist[index] + nextWeight

다음과 같은 값임

 int cost = pq.top().second;
   ...
dist[nextNode] vs cost  + nextWeight

🔑 풀이 핵심

• 우선순위큐로 가장 작은 간선부터 탐색하기
• 정점 업데이트 시에는 다른 경로로 해당 정점까지 오는 비용(저장된 비용) vs 이전 정점거쳐 해당 정점까지 오는 비용을 비교하여 업데이트하기
• 우선순위큐에 다음으로 탐색할 정점정보를 넣을 때, 새로 업데이트 된 비용 정보를 넣기
• INF는 간선 가중치의 최대값 * (정점 개수 -1) 보다 큰 값을 사용해야 함
• 이번 문제는 visited 배열이 굳이 필요 없음
  방문 체크는 우선순위 큐에서 나온 거리가 현재 거리 배열에 저장된 값과 같은지를 비교하는 것으로 방문 체크가 가능.
• 간선 정보는 인접 행렬이 아니라 인접 리스트로 저장해야 함.

while(!pq.empty()){
        int index = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        for(int j = 0; j< map[index].size(); j++){
            pair<int,int> next = map[index][j];
            int nextNode = next.first;
            int nextWeight = next.second;
            if(dist[nextNode] > cost + nextWeight){
              dist[nextNode] = cost + nextWeight;
              pq.push({nextNode, cost + nextWeight});
            }
        }
    }