BOJ 1753 - 최단 경로

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

1753번: 최단경로

 

 

다익스트라 알고리즘을 이용해서 푸는 문제로,

 

다익스트라 알고리즘은 아래와 같다

 

 

* 다익스트라

다익스트라 알고리즘은 한 개의 정점을 시작 정점으로 하여 다른 모든 정점 간의 최단 거리를 구하는 알고리즘 이다.

문제에 제시된 "예제입력1"을 근거로 그래프를 그려서 예로 들면..

대략 이런 모양이고, 1번 노드를 시작점으로 하여 다른 노드간 최단 거리를 탐색하려면 아래 과정을 거쳐야 한다.

 

 

먼저 힙(우선순위 큐)을 이용해서 문제를 풀어야 하며, 거리를 담는 dist 배열이 필요하다

첫 시작을 1번 노드 부터 시작하므로, 이에 대한 우선순위 큐와 dist 배열은 아래와 같다

 

PQ

dist 배열

1	2	3	4	5
0	INF	INF	INF	INF

 

PQ 테이블에서 i 는 정점 번호를, d 는 가중치 값을, p 는 이전 정점 번호를 의미한다.

1번 정점부터 시작할 때는 시작점 자신 i = 1 에 대한 d 값은 당연히 0 이며, 이전정점 p 또한 없다

INF 는 무한대를 의미하며, 다익스트라 알고리즘을 구현할 때 첫 시작 초기화 값은 무한대로 잡고 시작한다

(왜냐하면, 연결되지 않은 정점간 거리는 무한대로 표기하기 때문에 첫 시작시에 무한대로 잡고해야 최소값 비교가 가능하기 때문이다)

 

dist 배열에선 1번에서 시작했으므로, dist[1] = 0 이며, 나머지는 무한대값으로 처리한다.

 

 

다음 작업으로, 힙(우선순위 큐) 맨 앞에 있는 1번 노드를 꺼내고, 인덱스 값은 1, d = 0 이며, 

dist[1] 과 d 를 비교해서 dist[1] 이 더 작은 경우, 연산을 하지 않고, 같거나 큰 경우 연산을 수행한다.

dist[1] == d 이므로, 1번 주변의 인접 정점을 찾아서 거리 계산을 한뒤 더 적은 값을 큐에 넣는 작업을 한다

 

이때 거리 계산을 위한 기준식은 아래와 같이된다.

dist[x] = min(dist[x], dist[y] + adj[y][x])

(x 는 인접한 정점 번호, y 는 인접한 정점 번호를 계산하기 위한 기준 정점 번호이다. 여기선 1번에서 시작했으므로 y = 1 이며, x 는 1번과 인접한 2,3 번 정점이 된다)

 

위식에 따라 2번, 3번 정점에 대한 거리 계산을 수행하면,

 

dist[2] = min(dist[2], dist[1] + adj[1][2]) = 2;

dist[3] = min(dist[3], dist[1] + adj[1][3]) = 3; 

 

이에 따른 결과는 아래 같이 된다.

 

PQ

dist 배열

1	2	3	4	5
0	INF	INF	INF	INF
	2	3

 

 

다음 작업도 마찬가지로 힙(우선순위 큐) 에 맨 앞의 값을 빼내며, 

인덱스가 이번엔 i = 2 이며, d = 2, p = 1 이 된다.

dist[2] 와 d 를 비교하면, 서로 동일 값이므로, 인접노드 탐색 연산을 수행하고,

2번에 인접한 정점은 3, 4 번이 되며,

인접 정점에 대한 거리 계산을 수행한다

 

dist[3] = min(dist[3], dist[2] + adj[2][3]) = 3;

dist[4] = min(dist[4], dist[2] + adj[2][3]) = 7; 

 

PQ

dist 배열

1	2	3	4	5
0	INF	INF	INF	INF
	2	3
			7

 

다음 연산에도 힙(우선순위 큐)에서 가장 맨 앞 값을 빼서 조건을 확인한다

이때 인덱스 번호는 i = 3, d = 3, p = 1 이다.

dist[3] 와 d 를 비교 했을 때, 서로 같으므로, 3에 대한 인접 정점을 탐색하고,

3의 인접 정점은 4 이다.

 

dist[4] = min(dist[4], dist[3] + adj[3][4]) = 7;

이 되며, 결국 같으므로 dist 배열엔 변화가 없고 PQ 에서만 top 이 pop 된다.

PQ

dist 배열

1	2	3	4	5
0	INF	INF	INF	INF
	2	3
			7

 

다음 작업도 마찬가지로, 큐에서 빼낼때, 3번 인덱스 이므로, 동일한 결과를 갖게 된다.

PQ

dist 배열

1	2	3	4	5
0	INF	INF	INF	INF
	2	3
			7

 

마지막으로, 4번 인덱스를 빼내면

d= 7 이며, dist[4] 와 동일한 값을 갖는다.

그러나 4번 노드가 인접한 노드가 없으므로 연산은 종료되고

최종적으로 큐가 비게 되어 반복문을 빠져 나간다.

 

최종적으로 dist 배열은 0, 2, 3, 7, INF 의 값을 갖게 된다.

 

1753 번에 대한 코드는 아래와 같다.

 

- c++

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int V, E, K;
int INF = 987654321;
vector<pair<int, int>> adj[20001];
int dist[20001];
 
void dijkstra(int start)
{
    dist[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start)); 
 
    while (!pq.empty())
    {
        int distance = -pq.top().first; 
        int current = pq.top().second;
        pq.pop();
        
        if(dist[current] < distance)
            continue;
 
        for (int i = 0; i < adj[current].size(); i++)
        {
            int next = adj[current][i].first;
            int nextDistance = distance + adj[current][i].second;
 
            if (nextDistance < dist[next])
            {
                dist[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
}
 
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> V >> E;
    cin >> K;
 
    for (int i = 1; i <= V; i++)
    {
        dist[i] = INF;
    }
    
    
    for (int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }
 
    dijkstra(K);
 
    for (int i = 1; i <= V; i++)
    {
        if (dist[i] != INF) cout << dist[i] << '\n';
        else cout << "INF" << '\n';
    }
 
    return 0;
}

 

 

 

 

- 참조한 다른 링크

https://hsp1116.tistory.com/42

다익스트라 알고리즘(Dijkstra Algorithm)

 

https://www.youtube.com/watch?time_continue=632&v=611B-9zk2o4&feature=emb_logo

 

 

 

이 문제랑 똑같은 문제로

BOJ 1916 번 문제가 있다

www.acmicpc.net/problem/1916