[백준/c++] - 1753 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

 

 

 

 다익스트라 알고리즘을 학습한 후 예제문제를 풀어봤다. 방향이 존재하는 가중치 그래프에서 시작 지점으로부터 최단 경로를 찾는 대표적인 예제 문제이다.

 

 

 

 

 

 

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>

using namespace std;

struct Vertex {
	int vertex;
	int cost;

	bool operator<(const Vertex v) const {
		return this->cost > v.cost;
	}
};

int E, V, K;
vector<vector<Vertex>> adjacent; // 인접 행렬 방식이 아닌 인접 리스트 방식으로 -> 메모리초과 때문에
priority_queue<Vertex> dijikstraQueue;
vector<int> best;

void Input() {
	cin >> V >> E;
	cin >> K;

	adjacent.resize(V + 1);
	best.resize(V + 1);
	fill(best.begin(), best.end(), INT_MAX);

	for (int i = 0; i < E; i++) {
		int start, dest, cost;

		cin >> start >> dest >> cost;

		adjacent[start].push_back(Vertex{dest, cost});
	}
}

void dijikstra(int start) {

	best[start] = 0;
	dijikstraQueue.push(Vertex{ start, 0 });

	while (dijikstraQueue.empty() == false) {

		Vertex curV = dijikstraQueue.top();
		dijikstraQueue.pop();

		// 2. 가장 비용이 낮은 간선을 꺼낸 후, 현재 최저 비용과 비교
		if (best[curV.vertex] < curV.cost)
			continue;

		// 이 이후로 해당 노드를 방문 처리한 것이 됨


		// 3. 인접한 간선들을 우선순위 큐에 추가
		for (int i = 0; i < adjacent[curV.vertex].size(); i++) {
			int dest = adjacent[curV.vertex][i].vertex;
			int edgeCost = adjacent[curV.vertex][i].cost;

			int nextCost = best[curV.vertex] + edgeCost; // 인접 간선을 포함하는 새로운 경로의 비용
			if (nextCost < best[dest]) {
				// 기록 갱신
				best[dest] = nextCost;
				dijikstraQueue.push(Vertex{ dest, nextCost });
			}
			else {
				continue;
			}
			
		}

	}

}

void printAnswer() {

	for (int i = 1; i <= V; i++) {
		int cost = best[i];

		if (cost == INT_MAX) {
			cout << "INF" << endl;
		}
		else {
			cout << cost << endl;
		}
	}
}

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


	Input();
	dijikstra(K);
	printAnswer();
}

 

 

 

 

 priority_queue를 이용하여 시작 지점으로부터 경로의 비용이 낮은 정점순으로 뽑혀나오게 하였다. 우선 순위 큐에서 가장 비용이 낮은 정점을 꺼내고 해당 정점이 현재 최단 거리와 비교하여 더 비용이 낮은 지 확인 후 방문. 그 이후 해당 정점과 인접한 간선들을 포함하는 경로가 현재 최단 거리인지 확인 후 최단 거리라면 우선 순위 큐에 넣어서 방문을 예약하는 방식이다.

 

 

 

 

 

 기본적으로 BFS와 유사한 방식이며 차이라고 한다면 다익스트라는 가중치가 있는 그래프에서 사용한다는 점, 우선순위 큐를 사용하여 가장 가까운 정점부터 방문한다는 점이 다르다. BFS의 경우 큐를 사용하므로 발견한 순서그대로 방문하기 때문에 어느정도 차이가 있다.

 

 

 

 

 

 

 

 

 참고로 문제를 풀면서 메모리초과가 계속떠서 무슨 문제인가 했는데, 정점의 개수가 최대 20000개라서 인접 행렬 방식을 사용하면 안된다. 그래서 막바지에 부랴부랴 인접 리스트 방식으로 바꾸기 위해 시간을 많이 날렸다. 다음부터는 최대 정점의 개수가 많을 때는 그냥 처음부터 인접 리스트 방식으로 구현하려고 해야겠다.

 

 

 

 

 

 

 

 

 

 인접 리스트와 인접 행렬 방식은 예전의 글에서 다뤘었다.

 

https://teachingforme.tistory.com/37

[자료구조] - 그래프(Graph)