[백준 1753번 C++] 최단경로

1. 문제 링크

www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

2. 문제 설명

가중치가 있는 방향 그래프의 정점의 개수, 간선의 개수, 시작 정점의 번호, 간선을 입력받아

시작점에서 다른 모든 정점으로의 최단 거리를 출력하는 문제입니다.

한 정점에서 다른 모든 정점으로의 최단 거리를 구하는 문제이고,

가중치가 10 이하의 자연수(음수가 아님)이기 때문에 다익스트라 알고리즘을 사용했습니다.

다익스트라 알고리즘의 개념과 코드는 아래 링크를 참고했습니다.

blog.encrypted.gg/918?category=773649

 

 

 

3. 소스코드

BOJ 1753번 최단경로 C++ 풀이입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int dis[20001];
const int INF = 2147483647;
vector<pair<int, int> > adj[20001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int V, E, K;
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(w, v));
	}
	fill(dis, dis + V + 1, INF);

	dis[K] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push(make_pair(dis[K], K));
	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		pq.pop();
		int dist = cur.first;
		int idx = cur.second;
		if (dis[idx] != dist)
			continue;
		for (int i = 0; i < adj[idx].size(); i++) {
			pair<int, int> next = adj[idx][i];
			int cost = next.first;
			int nidx = next.second;
			if (dis[nidx] > dist + cost) {
				dis[nidx] = dist + cost;
				pq.push(make_pair(dis[nidx], nidx));
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (dis[i] == INF)
			cout << "INF\n";
		else
			cout << dis[i] << "\n";
	}

	return 0;
}

7번 라인 : 시작점에서 다른 모든 정점으로의 최단거리를 저장할 배열 dis를 선언합니다. 정점의 최대 개수가 20000이므로 dis[20000]으로 접근할 수 있도록 20001의 크기로 선언했습니다.

8번 라인 : 무한대를 표현하기 위해 int의 최댓값을 INF라는 상수로 선언했습니다.

9번 라인 : 간선을 인접리스트형태로 저장하기 위해 vector 배열 adj을 선언했습니다. 정점 번호와 가중치를 함께 저장해야 하기 때문에 pair를 사용했습니다.

20번 라인 : 입력받은 간선을 adj에 추가합니다. 아래에서 priority queue를 사용하여 min heap을 만들 때 가중치를 기준으로 정렬해야 하므로 가중치(w), 정점 번호(v)순으로 pair를 만들어서 추가합니다.

22번 라인 : dis배열을 INF로 초기화합니다.

24번 라인 : 시작점에서 시작점으로의 거리는 문제에서 제시한대로 0으로 바꿔줍니다.

25번 라인 : priority_queue를 선언합니다. priority_queue<자료형, 구현체, 비교 연산자>의 형태로 사용해야 하므로 구현체는 기본값인 vector를 사용했고, 비교 연산자는 greater를 사용하여 min heap을 만들었습니다. (참고 링크 : koosaga.com/9)

26번 라인 : pq에 시작점을 추가합니다.

27번 라인 : 힙이 비어있지 않는 동안

28 ~ 31번 라인 : 가중치가 가장 작은 간선을 꺼내서 dis에 가중치를, idx에 정점을 저장합니다.

32 ~ 33번 라인 : dis[idx]와 dist가 다르면, 이전에 저장할 때보다 더 짧은 경로를 찾은 것이므로 continue합니다.

34번 라인 : 인접 리스트에서 idx번 정점과 연결되어 있는 간선을 모두 돌면서

35 ~ 37번 라인 : cost에 가중치, nidx에 다음 정점을 저장하고,

38번 라인 : 현재 저장되어 있는 최단 거리(dis[nidx])보다 dist + cost한 값이 작으면

39 ~ 40번 라인 : dis[nidx]에 dist + cost를 저장하여 최단 거리를 갱신하고, pq에 추가합니다.

44 ~ 49번 라인 : 1번 정점부터 V번 정점까지 돌면서 경로가 존재하지 않는 경우에는 INF를 출력하고, 시작점부터 i번째 점까지의 최단 거리를 출력합니다.