[C++] 1753: 최단경로

쩡우·2022년 11월 23일

BOJ algorithm

목록 보기

8/65

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1

예제 출력 1

0
2
3
7
INF

풀이

전형적인 다익스트라 알고리즘 문제.
처음에는 queue를 사용하지 않고, 다익스트라 수학 문제를 풀듯이 모든 노드를 순회하면서 가중치가 가장 작은 노드를 찾아, 그 인접 노드를 갱신하는 방식으로 풀었는데 시간 초과가 떠서 ㅠ-ㅠ
찾아보니 우선순위 큐(priority queue)라는 자료형을 활용할 수 있어서 우선순위 큐를 통해서 풀어 봤다! 우선순위 큐를 사용하면 다음에 가야 할 노드가 top에 있게 되기 때문에 모든 노드를 순회하지 않아도 빠르게 찾을 수 있다.

[index] 노드의 현재까지 확인한 최단 거리값을 저장해 놓는 path array를 만들어 주고, 무한 대신 -1로 초기화했다.
그래프는 pair를 포함하는 2차원 vector로 구현하였고, pair에는 (연결된 노드 이름, 가중치)를 넣어주었다.
우선순위 큐는 노드의 이름(int)을 넣어주고, 노드 i의 현재 최단 거리값(path[i])를 기준으로 오름차순으로 정렬되게 하였다. -> cmp라는 비교함수를 따로 만들어주었다.

풀이 방법은 다음과 같다.

먼저 start_voltex를 큐에 넣고, start_voltex 위치의 가중치를 0으로 둔다.
큐가 빌 때까지 while문을 돌린다. 큐의 제일 위(앞)에 있는 값(=방문한 노드과 인접한 노드들 중 방문 시 가중치가 가장 작은 노드)을 now_voltex로 두고, pop한다.
그래프를 확인하여 now_voltex와 인접한 target_voltex를 모두 확인한다.
해당 target_voltex의 path array 값을 확인한다.
(a). path[target_voltex]가 -1(무한)이면, path[target_voltex]를 갱신한다.
(b). path[target_voltex]가 path[now_voltex]와 target_weight를 더한 값보다 크면, (path[now_voltex] + target_weight)로 갱신한다.
해당 target_voltex가 4번의 두 경우 중 하나에 해당된다면, 큐에 target_voltex를 push한다.

코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

void input_data(void);
void shortest_path(void);
void print_result(void);

vector<vector<pair<int, int>>> graph;

int	path[20001];
int total_voltex, total_edge, start_voltex;

struct cmp
{
  	bool operator() (int a, int b) 
	{
		return path[a] > path[b];
	}
};

priority_queue<int, vector<int>, cmp> p_queue;

int main(void)
{
	input_data();
	shortest_path();
	print_result();

	return (0);
}

void input_data(void)
{
	cin >> total_voltex >> total_edge;
	cin >> start_voltex;

	graph.assign(total_voltex + 1, vector<pair<int, int>>(0));
	fill(&path[0], &path[20001], -1);
	path[start_voltex] = 0;

	int	i = 0;
	while (++i <= total_edge)
	{
		int u, v, weight;
		cin >> u >> v >> weight;
		graph[u].push_back(make_pair(v, weight));
	}

	return ;
}

void shortest_path(void)
{
	p_queue.push(start_voltex);
	path[start_voltex] = 0;
	
	while (!p_queue.empty())
	{
		int now_voltex = p_queue.top();
		p_queue.pop();

		int i = -1;
		int now_edges = graph[now_voltex].size();
		while (++i < now_edges)
		{
			int target_voltex = graph[now_voltex][i].first;
			int target_weight = graph[now_voltex][i].second;

			if (path[target_voltex] == -1 || path[target_voltex] > path[now_voltex] + target_weight)
			{
				path[target_voltex] = path[now_voltex] + target_weight;
				p_queue.push(target_voltex);
			}
		}
	}

	return ;
}

void print_result(void)
{
	int i = 0;

	while (++i <= total_voltex)
	{
		if (path[i] == -1)
			cout << "INF";
		else
			cout << path[i];
		cout << '\n';
	}

	return ;
}