[백준/C++]최단경로

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 시작점에서 다른 정점에 도착하는 최단 경로를 구하는 문제다.

 

최단 경로를 구하는 알고리즘에는 다익스트라(Dijikstra) 알고리즘이 있다.

 

다익스트라 알고리즘은 아래 순서로 진행된다.

 

1. 방문하지 않은 정점 중에서 가장 비용이 적은 방문할 수 있는 정점을 선택한다.

2. 선택한 정점에서 이동할 수 있는 정점들을 방문할 수 있는 정점에 추가하고, 이동했을 때 드는 비용을 갱신한다.

3. 선택한 정점을 방문처리하고, 다시 1번 과정을 반복한다.

 

이 과정에서 가장 비용이 적은 방문할 수 있는 정점을 선택하는 방법에 따라 시간복잡도가 달라진다.

 

만약 V개의 노드를 전부 탐색할 경우 O(V^2)의 시간복잡도를 갖게 된다. 

(V개의 노드 중 방문한 적이 없으면서 비용이 가장 적은 노드를 비교해 찾아야 하기 때문)

 

Priority Queue와 같은 자료구조를 사용하면 O(Elog(E)) 의 시간복잡도를 갖게 된다.

(만약 중복간선이 없다면, E의 최대값은 V*(V-1)이므로 O(Elog(V))가 된다.

 

이 문제에서는 V가 20,000 E가 300,000이므로 Priority Queue의 자료구조를 활용해 문제를 해결했다.

 

이후 각 정점에 도착하는 최단경로를 출력하면 된다.

 

+ 중복 간선이 있어도 최소 비용을 저장하기 때문에 신경 쓸 필요는 없다.

 

 

​

[아이디어 정리]

1. Priority Queue를 이용한 다익스트라 알고리즘으로 문제를 푼다. (시간복잡도 O(Elog(E))
2. 이후 정점에 방문할 때 최단 경로 값을 저장한 visited 배열을 만들고, Priority Queue가 빌 때 까지 진행한다.
3. 탐색이 완료된 후 visited 에 저장된 값이 초기값이라면 INF를 출력하고, 초기값이 아니면 저장된 값을 출력한다.

 

 

Code

 

 

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

struct cmp {
	bool operator() (const pair<int, int> a, const pair<int, int>b) const {
		return a.second > b.second;
	}
};


const int INF = 1000000000;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int V,E;
	cin >> V >> E;
	int stNode;
	cin >> stNode;
	vector<vector<pair<int,int>>> graph(V + 1);
	int u, v, w;
	for (int i = 0; i < E; i++) 
	{
		cin >> u >> v >> w;
		graph[u].push_back(make_pair(v, w));
	}
	vector<int> visited(V + 1, INF);
	priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;
	q.push(make_pair(stNode, 0));
	visited[stNode] = 0;
	pair<int, int> np;
	while (!q.empty()) 
	{
		np = q.top();
		q.pop();
		if (np.second > visited[np.first]) {
			continue;
		}
		for (int i = 0; i < graph[np.first].size(); i++) 
		{
			int nextNode = graph[np.first][i].first, pc= graph[np.first][i].second;
			if (visited[nextNode] > np.second + pc) 
			{
				visited[nextNode] = np.second + pc;
				q.push(make_pair(nextNode, np.second + pc));
			}
		}
	}
	for (int i = 1; i <= V; i++) 
	{
		if (visited[i] < INF) {
			cout << visited[i] << "\n";
		}
		else {
			cout << "INF\n";
		}
	}

	return 0;
}

 

---

최단 경로 문제를 풀 때, 항상 Priority Queue를 이용한 다익스트라 알고리즘이 효율이 좋은건 아니기 때문에 문제의 상황에 맞게 고려를 해야 하는 점을 잊지 말자

 

1753번: 최단경로