[c++] 백준 - 최단경로

최단경로 성공

시간제한 메모리제한 제출 정답맞은사람 정답비율

1 초

256 MB

98993

27161

13160

23.735%

알고리즘 분류

• 그래프 이론
• 다익스트라

https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 20000+1;
const int INF = 98765432;
vector<pair<int, int> >Edge[MAX];
int Distance[MAX];
int V, E, Start;

void Input(){

   cin>>V>>E>>Start;
   for(int i=0;i<E;i++)
   {
      int u, v, w;
      cin>>u>>v>>w;
      Edge[u].push_back(make_pair(v, w)); //출발 - 도착,비용
   }
}

void Dijkstra(){
   for(int i=1;i<=V;i++)
      Distance[i] = INF; //Dist 배열을 무한대로 초기화
   priority_queue<pair<int, int> > pq;

   Distance[Start] = 0; //시작 정점의 Dist를 0으로
   pq.push(make_pair(0, Start)); //비용, 시작위치 푸쉬

   while(pq.empty()==0){
      int NowCost = pq.top().first*-1; //최소를 뽑아야함으로 -1을 곱하였다.
      int Now = pq.top().second;
      pq.pop();

      for(int i=0;i<Edge[Now].size();i++)
      {
         int NextCost = Edge[Now][i].second;
         int Next = Edge[Now][i].first;

         if(Distance[Next] > NowCost+NextCost){ //기존의 Dist가 더 크다면 대체함
            Distance[Next] = NowCost+NextCost;
            pq.push(make_pair(Distance[Next]*-1, Next)); //우선순위 큐에 다음 위치까지 거리,다음 푸쉬
         }
      }
   }

   for(int i=1;i<=V;i++)
   {
      if(Distance[i]==INF)
         cout<<"INF\n"; //endl은 느려서 시간초과, \n으로 대체함
      else
         cout<<Distance[i]<<"\n";
   }
}

int main() {
   //입출력 최적화하기
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
    
   Input();
   Dijkstra();

   return 0;
}

 

후기

 코딩테스트에서 아주 가끔 최단경로가 나올 수도 있어서 공부하였다. 구현방법을 보고 풀었다.

 python은 이런 그래프 문제에는 시간제한 때문에 불리해서 c++을 사용하는 것이 좋을 것 같다.

 최단경로 문제 풀이에는-다익스트라, 벨만포드, 플로이드 와샬 등이 있다고 하는데, 다익스트라가 가장 일반적인 것 같다. 다익스트라는 특정 정점을 알고, 이 정점으로부터 다른 정점까지의 최단거리를 구하는데 사용된다고 한다.

이것을 응용해서, 다익스트라 함수를 구현 한 후, 여러 개의 정점을 각각 다익스트라를 사용하는 문제가 나올 것 같기도하다?

(참고로 간선 비용이 음수가 있을 경우는 다익스트라를 사용할 수 없다고 함)

 

풀이

* 다익스트라에서는 크게 3가지가 필요하다. 1)간선과 비용 정보를 가지고 있는 것(일반적으로 행렬)  ,2) 특정 정점으로부터 다른 정점까지의 최단 거리를 나타내는 Distance배열 , 3) 어떤 간선으로 이동할 것인지에 쓰이는 우선순위 큐(항상 최대한 최소비용을 찾으므로 그리디하다고 볼 수 있다)  

 

(1) 간선과 비용 정보를 가지고 있는 행렬을 입력받는다.

(2) Distance 배열을 만들고 INF로 초기화, 우선순위 큐를 만든다. Dist배열[시작정점] = 0 을 해주고, 우선순위 큐에다 (0, 시작정점위치)를 넣는다.

(3) 우선순위큐가 빌 때까지 반복한다. pq.top()*-1을 해줘서 pq에서 가장 낮은 비용을 가진 것을 뽑는다.(pq는 pair()에서 첫번째 요소가 대상이며, top에 가까울수록 값이 크다. 따라서 반대로 곱하기 -1을 해줌으로 최소를 뽑을 수 있다)

(4) 이것(next)비용과 현재 비용을 더한 것을 Dist[next]과 비교한다. Dist[next]가 오히려 크면, 새롭게 최단거리를 생성할 수 있다. Dist[next]를 next비용과 현재비용 더한 것으로 대체한다. 또한 pq에도 푸쉬한다.