[백준 / C++] 최단경로 (골드4, 1753)

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1

0
2
3
7
INF

---

문제 풀이

이번 문제는 가중치가 존재하는 맵에서 최단 경로의 길이를 구하는 다익스트라 문제입니다.

 

이론상으로만 알고 있던 알고리즘을 실제로 처음 구현해보느라 많은 뻘짓(?)을 하게 되었던 문제입니다.

 

특히 일반적인 다익스트라는 O(N * N) 시간복잡도를 가지고 있어 20,000개의 정점과 300,000개의 간선이 조건이라 시간 초과를 받을 것이며, 가장 가까운 노드를 체크하기 위해 우선순위 큐를 사용해 O(NlonN)까지 시간복잡도를 줄여야 하는데, 해당 부분을 처음 설계하다 보니 많은 실수가 있었습니다.

 

구현 아이디어에 대해 간단히 설명드리자면 다음과 같습니다.

1. visited 배열을 만들고 모두 MAX(최대값)으로 설정합니다.
2. 시작 지점을 우선순위 큐에 저장합니다. (start[노드 번호], 0[가중치]) - 시작 지점은 가중치가 0입니다.
3. 시작 지점으로 부터 연결된 모든 노드를 순회하며 다음 노드까지의 가중치 (현재까지의 가중치 + 다음 가중치)를 체크합니다.
4. 3에서 구한 다음노드까지의 가중치가 visited[다음노드] 에 저장된 가중치보다 작은 경우 값을 갱신하고 큐에 추가합니다.
5. 우선순위 큐가 빌 때까지 3 ~ 4를 반복합니다.

void BFS(int u)
{
    visited[u] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;

    // 시작지점 저장
    pq.push(make_pair(start, 0));

    while (!pq.empty())
    {
        int distance = pq.top().second;
        int current = pq.top().first;
        pq.pop();

        // 이미 체크한 경우 (이미 최적의 경로가 존재하는 경우)
        if (visited[current] < distance) continue;

        for (int i = 0; i < adj[current].size(); i++)
        {
            // 다음 노드까지의 비용 계산
            int newDistance = distance + adj[current][i].second;

            // 다음 노드까지의 비용이 더 작은 경우
            if (newDistance < visited[adj[current][i].first])
            {
                // 해당 값으로 갱신
                visited[adj[current][i].first] = newDistance;
                // 큐에 값 추가
                pq.push(make_pair(adj[current][i].first, newDistance));
            }
        }
    }
}

 

위 코드가 가장 중요하며, "이미 체크한 경우"를 따지는 부분에서 많은 실수가 있어,, 여러 시도 끝에 성공하게 되었습니다.

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int SIZE = 20002;
const int MAX = 987654321;

int V, E;
int start;
vector<pair<int, int>> adj[SIZE];

int visited[SIZE];

struct Comp
{
	bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
	{
		return p1.second > p2.second;
	}
};

void BFS(int u)
{
	visited[u] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;

	// 시작지점 저장
	pq.push(make_pair(start, 0));

	while (!pq.empty())
	{
		int distance = pq.top().second;
		int current = pq.top().first;
		pq.pop();

		// 이미 체크한 경우
		if (visited[current] < distance) continue;

		for (int i = 0; i < adj[current].size(); i++)
		{
			// 다음 노드까지의 비용 계산
			int newDistance = distance + adj[current][i].second;

			// 다음 노드까지의 비용이 더 작은 경우
			if (newDistance < visited[adj[current][i].first])
			{
				// 해당 값으로 갱신
				visited[adj[current][i].first] = newDistance;
				// 큐에 값 추가
				pq.push(make_pair(adj[current][i].first, newDistance));
			}
		}
	}
}

int main()
{
	cin >> V >> E >> start;

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].push_back(make_pair(v, w));
	}

	fill(visited, visited + SIZE, MAX);

	BFS(start);

	for (int i = 1; i <= V; i++)
	{
		if (visited[i] == MAX)
		{
			cout << "INF" << '\n';
		}
		else
		{
			cout << visited[i] << '\n';
		}
	}
}