문제: 1753번: 최단경로

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

// 0 번 인덱스는 안 쓸 거임요..
// first: 가중치, second: 연결 노드 번호
vector<pair<int, int>> linkedList[20001]; // 링크드 리스트

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

	int v, e; // v: 정점의 개수, e: 간선의 개수
	cin >> v >> e;

	int startNode; // 시작 정점 번호
	cin >> startNode;

	// 모든 정점에는 1부터 v까지 번호가 배겨져 있다..
	for (int i = 0; i < e; i++) {
		// 간선을 나타내는 세 개의 정수 u, v, w
		// u 에서 v 로 가는 가중치 w 인 간선이 존재한다는 의미
		int u, v, w;
		cin >> u >> v >> w;

		// 연결 정보 설정..
		linkedList[u].push_back(make_pair(w, v));
	}

	// 시작 정점으로부터 모든 정점까지의 최단 경로의 경로값을 출력해야함.
	// 즉 distance 배열을 하나 만들어서 거기에 시작 정점과의 거리를 저장하면 될 듯.

	// 거리는 초기값을 제일 큰 양수로 설정해놓을 것..
	vector<int> distance((v + 1), INT_MAX); // 인덱스 계산 편하게 하려고 v+1 만큼..

	vector<int> prev(v + 1); // 각 정점마다 이전 정점을 저장해놓기..

	// 현재까지 선택된 정점을 집합에 저장해놓기
	set<int> nodeSet;
	
	// 연결 가능한 대상들을 넣어놓기..

	// first: 가중치, second: 연결 정점 번호
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minNodes;
	minNodes.push(make_pair(0, startNode)); // 일단 맨 처음엔 시작 노드 넣어놓기
	distance[startNode] = 0; // 자기 자신과의 거리는 0

	while (!minNodes.empty()) {
		pair<int, int> node = minNodes.top(); // 가져오기(가중치 가장 작은 간선)
		int u = node.second;
		minNodes.pop();

		// 집합에 존재하지 않으면 find 함수는 nodeSet.end() 값을 반환함
		if (nodeSet.find(u) != nodeSet.end()) continue; // 즉 이미 존재할 땐느 그냥 포기

		// 존재하지 않으면 이제 집합에 넣어주기
		nodeSet.insert(u);

		// 집합에 새로 넣었으니까 이제 얘랑 연결된 정점들 정보도 업데이트 해야함.
		for (int i = 0; i < linkedList[u].size(); i++) {
			int v = linkedList[u][i].second; // u 와 연결된 정점 번호
			int w_uv = linkedList[u][i].first; // u 와 v 사이의 가중치

			// v 가 집합에 존재하지 않아야 하고, 새로 넣으려는 가중치 값이 기존 시작점과 v 와의 가중치 값보다 작아야함.
			if ((nodeSet.find(v) == nodeSet.end()) && distance[u] + w_uv < distance[v]) {
				distance[v] = distance[u] + w_uv; // 거리 값 업데이트
				prev[v] = u;
				minNodes.push(make_pair(distance[v], v));
			}
		}
	}

	// 출력
	for (int i = 1; i < v + 1; i++) {
		if (distance[i] == INT_MAX)
			cout << "INF" << "\n";
		else 
			cout << distance[i] << "\n";
	}
		


	return 0;
}

 

어제 풀었던 문제랑 다를 바가 없는 문제였다. 그나마 다른게 있다면 시작 정점으로 부터 모든 정점까지 개별로 최단 거리를 출력해야 한다는 점이다.

각 점까지의 최단경로는 반복문을 돌다보면 알아서 구해지게 되므로 마지막에 출력할 때 1부터 v+1 까지 돌면서 distance 배열에 저장해둔 값을 출력해주면 된다.

최단 거리가 존재하지 않는 정점은 INF 를 출력해야 하는데 이를 어떻게 해결했냐면 추가적인 과정 필요없이 그저 현재 distance 의 요소값이 INT_MAX 값과 같으면 INF 를 출력하도록 했다. 

 

distance 는 맨 처음 생성시 모든 요소의 값을 INT_MAX 로 출력해놨기 때문에 해당 정점이 다른 정점과 아무런 연결도 없으면 그대로 INT_MAX 값을 유지하고 있다. 즉, 최단 거리가 존재하지 않는 경우와 이는 같은 상황을 의미하므로 위와 같이 처리했다.

 

오늘은 문제를 스스로 풀어서 기분이 좋았다.

티스토리툴바