[백준/알고리즘] 1753번 최단경로

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1753번

 

방향 그래프가 주어지면, 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하시오.

 

풀이 알고리즘 : 다익스트라 알고리즘

 

문제 설명 그대로, 한 정점에서 다른 정점으로의 최단 경로를 구하는 '다익스트라 알고리즘'을 이용해서 푸는 문제이다.

 

기존에 다익스트라 알고리즘을 간단하게 사용되는 경우나, 중첩 반복문으로 모든 경우를 다 탐색해서 구현하는 정도만 알고 있었는데, 이번 문제에서는 해당 방법으로는 풀 수 없었다.

 

정점의 개수 V가 20000이하의 자연수, 간선의 개수 E가 300000이하의 자연수이다. 단순하게 중첩 반복문으로 구현하게 되면 시간 초과가 굉장히 높은 확률로 발생할 것이다. 그래서 찾아보니 우선순위 큐(Priority Queue)를 이용해서, 시작점에서 거리가 가장 가까운 노드를 우선으로 탐색하는 형태로 구현하면 시간복잡도를 O(ElogV)에 구할 수 있었다.

 

알고리즘은 다음과 같다.

adj : 각 정점끼리의 연결된 간선을 저장

dist : 출발점에서 각각의 노드까지의 최소 거리를 저장

pq : 출발점에서 가장 가까운 노드를 <거리, 정점번호> 로 저장

checked : 이미 방문한 노드인지 저장

 

1. PQ에서 가장 가까운 노드(cur)를 꺼낸다. 만약 checked라면 다음 노드를 확인하고, 그렇지 않으면 checked를 true로 한다.

2. cur에 연결된 간선 중 최신화했을 때, 더 가까운 거리가 있으면 최신화 한다. 이 경우 PQ에 <최신화한거리, 정점번호>를 push한다.

 

이를 반복하면, 어느순간 checked배열이 모두 true거나, PQ가 비게 되므로 정지하게 된다.

이때 중요한 점은, 현재 방문하는 노드(cur)는 출발지에서 항상 최소 거리이다. 따라서, 이전에 현재 노드까지 방문하지 못했다면, 이번에 방문한 경우가 최소 거리이므로, checked배열에서 이후 방문하지 않도록 확인해 주는 점이다.

 

아래는 제출 코드이다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int v, e, stt, INF = 1000000000;
	cin >> v >> e;
	cin >> stt;
	vector< map<int,int> > adj(v + 1);
	vector<int> dist(v + 1, INF);	// stt에서 각 노드까지 거리
	dist[stt] = 0;	// 출발 노드

	// 경로를 입력
	for(int i = 0; i < e; i++) {
		int s, d, v;
		cin >> s >> d >> v;
		if(adj[s].find(d) != adj[s].end() && v < adj[s].find(d)->second) {
			// 기록된 길보다 짧은 길이 있는 경우
			adj[s][d] = v;
		} else if(adj[s].find(d) == adj[s].end()) {
			// 기록된 길이 없는 경우
			adj[s].insert(make_pair(d, v));
		}
	}

	// 노드 stt에서 가장 가까운 노드를 PQ에 입력
	// pair : (거리, 정점번호)
	priority_queue< pair<int, int>, vector< pair<int,int> >, greater< pair<int, int> > > pq;
	for(int i = 1; i < v + 1; i++) {
		pq.push(make_pair(dist[i], i));
	}

	// 방문한 노드인지 확인
	bool checked[v + 1] = {false};

	while(!pq.empty()) {
		int cur = pq.top().second;
		int d = pq.top().first;
		pq.pop();

		if(checked[cur]) continue;
		else checked[cur] = true;

		// cur에 연결된 노드 중 가까운 거리가 있으면 최신화
		map<int,int>::iterator it;
		for(it = adj[cur].begin(); it != adj[cur].end(); ++it) {
			int dest = it->first;
			int move = it->second;
			if(d + move < dist[dest]) {
				// 우회해서 이동하는 거리가 이전까지 최소거리보다 작을때
				dist[dest] = d + move;
				pq.push(make_pair(dist[dest], dest));
			}
		}
	}

	for(int i = 1; i < v + 1; i++) {
		if(dist[i] == INF) cout << "INF\n";
		else cout << dist[i] << "\n";
	}

	return 0;
}