[백준 BOJ] 1753_최단 경로

다익스트라에 대한 문제를 우선순위 큐를 사용하여 풀어보았다. 우선순위 큐는 최대 힙의 구조를 가지고 있는데, 최소 비용을 탐색해야하기 때문에, 비용 값을 음수화 하여 힙에 넣었다. 

 

이 코드는 내가 구현한 코드가 아니라https://jaimemin.tistory.com/555 의 코드를 참고하였다.

 

함수의 형태가 void나 int가 아닌 vector를 사용하였는데 이런식의 코드 구현은 처음해봤다. return값을 담는 부분을 유의해야 할 것같다.

 

우선, 전역변수는 다음과 같이 선언하였다.

#include<iostream>
#include<vector>
#include<queue>
const int MAX = 20001;
const int INF = 987654321;

using namespace std;
int V, E, K;
vector<pair<int, int>>graph[MAX];

정점의 개수는 최대 2만개이고, 1번부터 시작하므로 20001로 선언하였다.

 

main 입력 부분은 다음과 같다.

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> V >> E >> K;
	V++;//정점 번호 : 1부터 시작
	for (int i = 0; i < E; i++) {
		int source, destination, cost;
		cin >> source >> destination >> cost;
		graph[source].push_back({ destination, cost });
	}
 	vector<int> result = dijkstra(K, V); // 시작점, 정점의 개수
 }

source : 시작점, destination : 목적지, cost : 가중치(비용)이다. 

 

이후, dijkstra 함수를 호출한다. 이때의 파라미터 값은 시작지점, 정점의 개수이다. 또한 dijkstra 함수의 타입이 벡터이므로 저렇게 하면 result 벡터에 값이 들어간다. 이렇게 함수를 구현하는건 처음이라 좀 어색한데, 만일 데이터 타입이 int라고 가정하면 int result = dijkstra(K, V)이고 dijkstra 함수는 int dijkstra(int start, int vertex) 일 것이다.

 

다음은 dijkstra 함수를 나누어서 살펴보자.

vector<int> dijkstra(int start, int vertex) {
	vector<int>distance(vertex, INF); //start지점을 기준으로 거리
	distance[start] = 0; //자기 자신은 0
	priority_queue<pair<int, int>>pq; //cost, vertex
	pq.push({ 0, start }); // 비용과 정점 저장
    
    ...

우선 시작 지점부터 노드들 까지의 거리를 저장하는 distance 벡터를 선언한다. 벡터의 크기는 vertex, 초기화는 INF로 해준다.

 

시작지점이 1이고 정점이 5개라고 가정하면 현재 distance 벡터는 다음과 같은 모양이다.

[1]	[2]	[3]	[4]	[5]
0	INF	INF	INF	INF

 

최소 힙을 사용하기 위해 우선순위 큐에는 방문한 정점의 cost와 정점번호를 push 해준다.

 

while (!pq.empty()) {
		int cost = -pq.top().first; // 최소값을 저장하기 위해 음수로 저장했으므로 꺼낼때 다시 -를 붙인다.
		int curVertex = pq.top().second; // 현재 방문한 정점
		pq.pop();
	
		if (distance[curVertex] < cost) { // 현재비용이 더 적으면 굳이 더 갈필요가 없다
			continue;
		}
		//curVertex와 연결된 정점 전부 확인
		for (int i = 0; i < graph[curVertex].size(); i++) {
			int neighbor = graph[curVertex][i].first;
			int neighborCost = cost + graph[curVertex][i].second;

			// 최소 경로 발견 시 업데이트
			if (distance[neighbor] > neighborCost) {
				distance[neighbor] = neighborCost;
				pq.push({ -neighborCost, neighbor }); //최소 값을 꺼내기 위해 음수로 저장
			}
		}
	}
	return distance;
}

 

1. 현재 위치의 정점, 비용은 cost, curVertex에 저장하고, pop 한다. 우선순위 큐이므로 저장된 비용값들 중 가장 작은 비용을 가진 값이 나온다.
2. 해당 비용(cost)와 distance 벡터의 값과 비교한다. distance벡터에는 시작지점부터 curVertex까지의 가는데 비용의 합이 들어있다. 현재 cost=0, curVertex=1, distance[curVertex]=0이다. 이 경우 distance[curVertex]와 cost의 값이 같으므로 if 조건문의 결과가 false이다.
   
   • if 조건문이 true인 경우 : 큐에서 꺼낸 정점을 거치는 비용이 더 많이 들기 때문에 최소 비용을 갱신할 필요가 없다.  
   • if 조건문이 false인 경우 : curVertex와 연결된 정점들을 모두 확인하는 최소 비용을 갱신한다. 
     • graph[curVertex][i]는 현재 graph[curVertex]와 연결된 정점을 나타낸다. 
     • graph[curVertex][i]의 first는 정점이므로 neighbor에, second는 비용이므로 우선순위 큐에서 꺼낸 cost와 second 값을 더하여 neighborCost에 저장한다.
     • 더하는 이유는 시작정점부터 다른 정점을 거쳐서 해당 정점으로 가는 비용이 들어있기 때문이다
3. for loop 내의 조건문
   • distance[neighbor] > neighborCost 가 참인 경우는 distance의 초기값은 INF로 되어있으므로 새롭게 연결된 정점일 경우 성립한다. 이 때 distance[neighbor]의 값이 neighborCost로 갱신된다.
   • 이 때의 비용이 우선순위 큐에 push 된다. 최소 힙을 구현하기 위해 cost값은 음수로 push 한다.

 

사실 아직 완벽하게 다익스트라 알고리즘 구현을 이해하지 못했다. 여러 문제를 풀어보며 더 익혀야겠다.