[백준 1753] 최단 거리

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

1753번: 최단경로

#include <cstdio>
#include <queue>
#include <list>
#include <algorithm>
int V, E;
int K;
int chk[20000 + 10];
int ans[20000 + 10];

using namespace std;

struct _st
{
	int n;
	int c;
};

struct COMP
{
	bool operator()(_st &a, _st &b) {
		return a.c > b.c;	// 가중치가 작은 노드를 기준으로 탐색한다.
	}
};

priority_queue<_st, vector<_st>, COMP> PQ;
list<_st> adj[20000 + 10];

void input(void)
{
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	for (int i = 0; i < E; i++) {
		int u = 0; int v = 0; int w = 0;
		scanf("%d %d %d", &u, &v, &w);
		adj[u].push_back({ v, w });
	}
}


void BFS(void)
{
	fill(chk + 1, chk + V + 1, 0x7fffffff);
	
	PQ.push({ K, 0 });	// 시작점 자신은 0을 출력한다. 
	chk[K] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		for (auto next : adj[data.n]) {
			int nn = next.n;
			int nc = data.c + next.c;
			if (chk[nn] <= nc) continue;
			chk[nn] = nc;
			PQ.push({ nn, nc });
		}
	}
}


void output(void)
{
	for (int i = 1; i <= V; i++) {
		if (chk[i] == 0x7fffffff) printf("INF\n");
		else printf("%d\n", chk[i]);
	}
}



int main()
{
	input();
	BFS();
	output();
	return 0;
}

이 문제에서 특히 고려해야 할 점은 다음의 두 가지 이다. 

 

1. 우선순위 큐를 활용해야 한다. 

그냥 큐를 통해 BFS를 구현했다면 시간초과가 날 것이다. 현재 노드에서 다음 노드로 이동하고자 할 때, 두 노드를 잇는 간선의 가중치가 가장 작은 경로를 우선적으로 탐색하는 우선순위 큐를 사용해야 한다. 

 

2. 인접 리스트를 활용해야 한다. 

문제에서 노드의 수(V)가 20,000 까지 많아질 수 있다. 따라서 20,000 * 20,000 인접행렬을 만들면 아주 높은 확률로 메모리 초과가 날 것이다. 따라서 인접한 노드의 정보만을 저장하여 효율적인 탐색을 돕는 인접 리스트를 사용해야 한다.

 

 

나머지 로직은 BFS 함수로 최단 거리/경로/시간 등등 구하는 것과 동일하다. 

다만 시작 정점(K)에서 모든 정점으로의 최단 경로를 구해야 하기 때문에, 특정 노드에 도착했다고 하여 BFS를 중단하는 것이 아니라, 끝까지 돌면서 각 정점으로의 최단 경로를 구하고 그것을 chk배열에 저장해 주었다.

이렇게 하면 마지막에 output 함수에서 for 루프 한번으로 정답을 출력할 수 있다.