[C++/BOJ] 백준 1753 최단경로(다익스트라)

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

1753번: 최단경로

 

정답 코드:

#include<iostream>

#include<queue>

#include<vector>

using namespace std;

int v, e, start;

using PI = pair<int, int>;

#define INF 2e9;

int visit[20001];

int dist[20001];

vector<vector<PI>> V;

priority_queue<PI, vector<PI>, greater<PI> > q;

int main() {

        cin >> v >> e >> start;

        V.resize(v + 1);

        for (int i = 0, p1, p2, p3; i < e; i++) {

                cin >> p1 >> p2 >> p3;

                V[p1].push_back({ p2,p3 });

        }

        fill(dist, dist + v + 1, 2e9);

        dist[start] = 0;

        q.push({ 0,start });

        while (!q.empty()) {

                int cur;

                do {

                cur = q.top().second;

                q.pop();

                } while (!q.empty() && visit[cur]);

              if (visit[cur] == 1) break;

              visit[cur] = 1;

              for (auto& i : V[cur]) {

                      int next = i.first;

                      int ndist = i.second;

                      if (dist[next] > dist[cur] + ndist) {

                               dist[next] = dist[cur] + ndist;

                               q.push({ dist[next],next });

                      }

              }

        }

        for (int i = 1; i <= v; i++) {

                if (dist[i] == 2e9) cout << "INF" << "\n";

                else cout << dist[i] << "\n";

        }

}

 

풀이 방법 :

우선순위큐(오름차순)과 벡터를 이용하여 다익스트라를 구현한다.

 

1) priority_queue선언

 

pair<int,int>은 using PI = pair<int,int> 

를 이용하여 가독성을 높힌다.

 

priority_queue<PI, vector<PI>, greater<PI> > q;

원래 우선순위큐는 높은게 먼저 나온다.

이른 반대로 낮은순으로 해야하기에 위와 같이 선언한다.

 

2) 입력과 resize

V.resize(v + 1);
for (int i = 0, p1, p2, p3; i < e; i++) {
            cin >> p1 >> p2 >> p3;
            V[p1].push_back({ p2,p3 });
}

 

 

v(소문자)는 노드의 개수이다.

V(대문자)는 간선의 연결과 가중치를 담는 벡터이다.

원래 벡터는 0부터 시작하므로 그냥 v를 주게되면 0~v-1으로 크기가 설정된다.

우리는 v도 사용해야하므로 v+1으로 설정한다.

 

3) Queue가 비어있지않을동안!

 

do while문을 사용하여 top에 있는 (길이가 가장 작은)

노드번호가 방문한적없는 노드(!visit[cur])를 찾아줍니다.

 

그 노드와 연결된 노드의 길이를 ndist로 저장합니다.

 

if (dist[next] > dist[cur] + ndist) {
         dist[next] = dist[cur] + ndist;
         q.push({ dist[next],next });
}

연결된 노드까지의 dist가 (현재노드 + 현재노드에서 연결된노드까지의 길이)보다 크다면

갱신해주고 큐에 넣어줍니다.

 

큐가 비게 되면 끝납니다.

 

4) 출력

for문을 이용하여 출력해줍니다.

갱신되지않았을 경우 => INF출력

갱신된경우 => 해당 dist출력

 

 

 

문제 후기 :

다익스트라 문제를 처음 풀어보았다.

알고리즘 시간에 배웠지만 처음 구현해보니 해설을 보지않고는 할수없었다.

그래도 포스팅하면서 한줄한줄 이해했다.