백준 알고리즘 1753 (최단경로) - C++, Python

[문제] 백준 알고리즘 1753 (최단경로)

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

1753번: 최단경로

 

정점 V개와 간선 E개가 주어지고, 시작 정점이 주어진다.

E개의 줄에 걸쳐 간선 u -> 간선 v , 가중치 w가 주어진다.

 

다익스트라 알고리즘을 사용하는 문제이다.

다익스트라 알고리즘은 우선순위 큐(=힙 트리)를 활용하고,

O((V+E)logV)의 시간복잡도를 갖는다고 나와있다.

(> https://namu.wiki/w/다익스트라%20알고리즘)

다익스트라 알고리즘 - 나무위키

 

풀이 순서

 

1. 노드와 가중치를 graph에 저장한다.

2. INF(아주 큰 값) 값으로 가득 찬 배열을 V+1 크기로 만든다.

    - 방문 여부와 가중치 최단거리를 동시에 체크해주는 배열, dijk로 명명

3. 우선순위 큐에 시작 w = 0, 시작 정점 S를 push한다.

4. 큐에 아무 것도 남지 않을 때까지, 하나씩 pop()

5. 현재 w와 v, graph[v]가 가리키는 nw와 nv의 계산 경로를 비교한다.

6. 최단 경로라고 파악되면 큐에 push한다.

    - 작은 w 값의 순으로 우선순위를 주기 위해 -nw값을 넣어준다.

 

[C++]

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int V, E, S;
const int MAX = 20001;
const int INF = 1e9;
vector< pair<int, int> > graph[MAX];

vector<int> solve_dijk(vector<int> dijk) {
	priority_queue< pair<int, int> > pq;
	pq.push({ 0, S });
	dijk[S] = 0;
	while (!pq.empty()) {
		int w, v;
		w = -pq.top().first; // w 오름차순
		v = pq.top().second;
		pq.pop(); // pop
		if (dijk[v] < w) { // 이전 값보다 크면 생략
			continue;
		}
		for (int i = 0; i < graph[v].size(); i++) {
			int nw, nv;
			nw = graph[v][i].first;
			nv = graph[v][i].second;
			nw = nw + w;
			if (dijk[nv] > nw) { // 최단 경로일 경우
				dijk[nv] = nw; // 채택 후
				pq.push({ -nw, nv }); // 큐에 push 
			}
		}
	}
	return dijk;
}

int main() {
	scanf("%d %d", &V, &E);
	scanf("%d", &S);
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		graph[u].push_back({ w, v });
	}
	vector<int> dijk(V + 1, INF); // V+1 크기, INF 값으로 초기화
	dijk = solve_dijk(dijk);
	for (int i = 1; i < V + 1; i++) {
		if (dijk[i] == INF) {
			printf("INF\n");
		}
		else {
			printf("%d\n", dijk[i]);
		}
	}
}

 

[Python]

import sys
from heapq import heappop, heappush
# heap queue : w 순으로 queue 노드 정렬 (= priority queue)
V, E = map(int, sys.stdin.readline().split())
S = int(sys.stdin.readline())
graph = [[] for _ in range(V+1)]
dijk = [1e9] * (V+1)
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([w, v])

def solve_dijk():
    queue = []
    dijk[S] = 0  # 시작 w = 0
    queue.append((0, S))  # 시작 w = 0, v = S
    while queue:
        w, v = heappop(queue)  # w 기준 오름차순 heap queue
        if dijk[v] < w:  # dijk[v]를 처음 진행 or 작은 값만 진행
            continue
        for nw, nv in graph[v]:
            nw += w
            if dijk[nv] > nw:  # 이전보다 짧은 경로이면
                dijk[nv] = nw  # nv, nw를 채택
                heappush(queue, (nw, nv))  # push 하고 이어서 진행

solve_dijk()
for i in range(1, V+1):
    print('{}'.format(dijk[i] if dijk[i] != 1e9 else 'INF'))