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

#문제

1753번: 최단경로
https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

---

#접근방법

최단경로 알고리즘은 여러가지가 있다.

1. 다익스트라
2. 벨만 포드
3. 플로이드 워셜

이 문제는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이므로 다익스트라 알고리즘을 사용하는 것이 적절하다.
 
다익스트라 알고리즘은 배열을 사용하는 방법과 우선순위 큐(힙 구조)를 사용하는 방법이 있다.
 
배열을 사용하는 방법은 시간복잡도가 O(V^2)이고, 우선순위 큐를 사용하면 시간복잡도는 O(E+Vlog(V))이므로 이 문제에서는 우선순위 큐를 사용해야 시간안에 돌아갈 수 있다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

vector<pair<int,int> > node[20005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
int value[20005];

int main(){
	int n,e,k;
	int u,v,w;
	
	scanf("%d %d",&n,&e);
	scanf("%d",&k);
	
	for(int i=0;i<e;i++){
		scanf("%d %d %d",&u,&v,&w);
		node[u].push_back(make_pair(v,w));
	}
	
	for(int i=1;i<=n;i++)
		value[i] = INF;
	
	value[k] = 0;
	
	pq.push(make_pair(0,k));
	
	while(!pq.empty()){
		int x = pq.top().first;
		int U = pq.top().second;
		pq.pop();
		
		for(int i=0;i<node[U].size();i++){
			int V = node[U][i].first;
			int W = node[U][i].second;
			
			if(x+W<value[V]){
				value[V] = x+W;
				pq.push(make_pair(x+W,V));
			}
		}
	}
	
	for(int i=1;i<=n;i++)
		if(value[i]==INF) printf("INF\n");
		else printf("%d\n",value[i]);
	
	return 0;
}

 
다익스트라 알고리즘의 동작 과정은 다음과 같다.

1. 출발 노드를 설정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
5. 위 과정에서 3,4번을 반복한다.

위 알고리즘을 구현한 풀이를 설명하겠다.
 
해당 문제에서 V는 최대 20000까지 주어진다. u,v,w를 이차원배열로 저장하게 되면 20000*20000/2^20 = 약 381MB가 되므로 메모리 초과가 걸린다. 따라서 vector<pair<int,int> >를 사용하여 300,000개의 입력값만 저장시켜주었다.
 
우선순위 큐 priority_queue는 내림차순으로 기본값이 설정이 되어있다. 오름차순으로 설정하려면
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq; 이렇게 작성하면 된다.
 
출발 노드 k를 제외한 나머지 노드들의 거리를 무한 INF 으로 설정을한다.
출발 노드를 pq에 넣고 다익스트라 알고리즘을 시작한다.
 
pq에서 제일 위에있는 값을 저장하는 행위는 위 동작 과정 3번과 동일하다.
 
int x는 현재 노드의 가중치를 뜻하며 int U는 현재 노드를 뜻한다.
현재 노드 U에서 갈 수 있는 모든 노드를 반복문으로 접근해준다.
int V는 U에서 갈 수 있는 노드를 뜻하고, int W는 U에서 V로 가는 가중치를 뜻한다.
 
x+W<value[V]이면 최소 비용을 갱신 시켜주고 pq에 갱신한 값과 갱신된 노드를 넣어준다. 이 행위는 위 동작 과정 4번과 동일하다.
 
pq에 값들이 빌 때까지 3,4번의 동작 과정을 반복하면 value배열에 시작 노드 k에서 각 노드로 가는 거리의 최소값이 들어간다.
 
value배열을 출력하면 정답이다.

---

#성능

---

#정리

최단거리 알고리즘 : 다익스트라, 벨만 포드, 플로이드 워셜을 알고 있고,
 
해당 문제에 적절한 최단거리 알고리즘이 다익스트라인 것을 알고 있고,
 
해당 문제의 입력값의 범위를 보고 메모리 초과와 시간 초과가 걸리지 않도록 적절한 자료구조와 방법을 알고있고,
 
이를 구현할 수 있는 능력을 갖추고 있으면 풀 수 있는 문제였다.