다들 다익스트라를 배우고 이해는 한다.


아~ 계속 간선 길이를 늘려가면서 점마다 우선순위큐로 dp를 찍어주면 되는구나~


이해는 하고 기초 문제를 풀고 나면 다익스트라를 다 아는 것 같은 착각이 든다 ㅎㅎ



근데 이제 다익스트라를 조금만 꽈서 낸 문제면 풀질 못한다 ㅜㅜ


어느 알고리즘이나 응용이 어렵지만, 내가 느끼기엔 다익스트라가 유독 까다롭더라.


그래서 이제부터 좀 다양한 다익스트라 문제들을 올리려고 한다.


이 글을 호오오오옥시 읽는 분들도 아는 문제가 있으면 추천을 부탁드립니다.


---------------------------------------------------------------------------------------------------------------------------------------------------------------------



1) 백준 16118 달빛 여우


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


조금만 꽈서 낸 문젠데 세 번이나 틀리고 맞았다 ^^


여우의 경우 1번 정점부터 나머지 정점까지 최소경로의 길이는 순수 다익스트라로 구할 수 있다.


늑대의 경우 내가 현재 정점에 오기전에 2배 빠르게 왔는지, 느리게 왔는지 기억해야 한다.


그래서 나는 구현을 쉽게 할려고(정말?), 간선을 2배로 뿔렸다. 즉 2배 빨라지는 길, 2배 느려지는 길을 추가했다.


그러면 전에 빨라지는 길로 왔었다면, 이번엔 느려지는 길로만 갈 수 있게 된다.


dp(fox, wolf)에는 빠르게 왔는지, 느리게 왔는지를 둘 다 기록했다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long ll;
 
int n, m;
int a, b;
ll fox[4001], wolf[4001][2], c;
 
struct edge_f {
    int to;
    ll cost;
 
    bool operator< (const edge_f& e) const {
        return cost > e.cost;
    }
};
 
struct edge_w {
    int to;
    ll cost;
    bool fast; //길 종류
 
    bool operator< (const edge_w& e) const {
        return cost > e.cost;
    }
};
 
int main() {
    scanf("%d %d"&n, &m);
 
    vector<vector<edge_f>> vf(n + 1);
    vector<vector<edge_w>> vw(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %lld"&a, &b, &c);
        vf[a].push_back({ b, 2ll * c });
        vf[b].push_back({ a, 2ll * c });
 
        vw[a].push_back({ b, c, false });
        vw[a].push_back({ b, 4ll * c, true });
        vw[b].push_back({ a, c, false });
        vw[b].push_back({ a, 4ll *c, true });
    }
 
    //////////////////////여우
    memset(fox, -1sizeof(fox));
 
    priority_queue<edge_f> pqf;
    pqf.push({ 1, 0ll });
 
    while (!pqf.empty()) {
        edge_f e = pqf.top(); pqf.pop();
 
        if (fox[e.to] != -1) {
            continue;
        }
 
        fox[e.to] = e.cost;
 
        for (auto next : vf[e.to]) {
            if (fox[next.to] != -1) {
                continue;
            }
            pqf.push({ next.to, e.cost + next.cost });
        }
    }
    //////////////////////여우
 
    //////////////////////늑대
    memset(wolf, -1sizeof(wolf));
 
    priority_queue<edge_w> pqw;
    pqw.push({ 1, 0ll, true });
 
    while (!pqw.empty()) {
        edge_w e = pqw.top(); pqw.pop();
 
        if (wolf[e.to][e.fast] != -1)
            continue;
 
        wolf[e.to][e.fast] = e.cost;
 
        for (auto next : vw[e.to]) {
            if (wolf[next.to][next.fast] != -1)
                continue;
            
            if (e.fast != next.fast) { //종류가 다른 길로 가야 해
                pqw.push({ next.to, e.cost + next.cost, next.fast });
            }
        }
    }
    //////////////////////늑대
 
    int ans = 0;
    ll _min, _max;
    for (int i = 1; i <= n; ++i) {
        _min = min(wolf[i][0], wolf[i][1]);
        _max = max(wolf[i][0], wolf[i][1]);
 
        if (_min == -1) { //못 가는 노드가 있을 경우
            if (fox[i] < _max) {
                ans++;
            }
        }
        else {
            if (fox[i] < _min) {
                ans++;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


2) bitonic path


scpc 2차 예선 문제였는데 링크를 찾고 있습니다 ㅜ

'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 1753 최단경로  (0) 2017.09.09
다익스트라 도입  (0) 2017.07.11

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를 출력하면 된다.

예제 입력 

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

예제 출력 

0
2
3
7
INF



1. 접근


한 정점에서의 나머지로의 모든 최단 거리를 구해야 한다.


다익스트라 쓰라고 있는 문제




2. 풀이


다익스트라에 대한 설명은 과거 자료를 참고하자


http://js1jj2sk3.tistory.com/5?category=725666




3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
 
struct node {
    int cost, to;
    bool operator<(const node& n)const {
        return cost > n.cost;
    }
};
 
vector< vector<node> > map;
 
int v, e, start;
int x, y, w;
 
void dijkstra() {
    vector<int> dis(v + 1-1);
    priority_queue<node> pq;
 
    pq.push({ 0, start });
 
    int from, to, w1, w2;
    while (!pq.empty()) {
        from = pq.top().to;
        w1 = pq.top().cost;
        pq.pop();
 
        if (dis[from] != -1)
            continue;
 
        dis[from] = w1;
 
        for (auto node : map[from]) {
            to = node.to;
            w2 = node.cost + w1;
            if (dis[to] != -1)
                continue;
            pq.push({ w2, to });
        }
    }
 
    for (int i = 1; i <= v; ++i) {
        if (dis[i] == -1)
            printf("INF\n");
        else
            printf("%d\n", dis[i]);
    }
}
 
int main() {
    scanf("%d %d %d"&v, &e, &start);
 
    map.assign(v + 1vector<node>());
 
    for (int i = 0; i < e; ++i) {
        scanf("%d %d %d"&x, &y, &w);
        map[x].push_back({ w, y });
    }
 
    dijkstra();
 
    return 0;
}
cs


'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 16118 달빛 여우  (0) 2018.10.01
다익스트라 도입  (0) 2017.07.11

1. 접근


지금까지 최단경로 문제를 접근하는 알고리즘은 BFS 밖에 배우지 않았다.

하지만 BFS로는 간선에 가중치가 부여된 그래프에서의 최단경로를 풀 수 없다.

중간 노드를 거치는 경로의 간선 수는 많아도, 가중치의 합은 적은 경우를 반영해줄 수 없기 때문이다.

따라서 우리는 가중치가 부여된 최단경로 문제를 위해 다익스트라 알고리즘을 새로 배워야 한다.


다익스트라 알고리즘은 음의 가중치가 없는(0도 허용한다) 그래프에서, 한 노드에서 나머지 모든 노드들 까지의 최단경로를 구해준다.

음의 가중치를 가지는 그래프에서의 최단경로 문제는 플로이드-워셜 / 벨만포드 알고리즘 을 사용해야 한다고 한다..


이제부터 이 알고리즘이 어떻게 동작하는지 단계별로 살펴보자.


0. 정의

  • 집합 S = 방문한 노드들의 집합

  • d[N] = A노드에서 N까지의 최단 거리

  • 집합 Q = 방문하지 않은 노드들의 집합


1. 아직 확인되지 않은 d[x]는 모두 무한으로 초기화한다.


초기화가 실행된 후의 그래프. (노드 A에서 나머지 모든 노드들까지의 최단 경로를 구하고자 한다.)


2. 첫 루프 : 이웃 노드들을 방문하고 d[x]를 갱신한다.


첫 루프를 마치고 난 뒤의 그래프.

  • d[N]이 최소값인 노드 N을 Q에서 제거하고, S에 추가한다. 즉, N을 방문한다.

  • N의 이웃 노드와의 거리를 측정하여

  • d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)

  • d[B] = 10, d[C] = 30, d[D] =15 는 Infinity보다 작으므로 갱신된다.


3. 두 번째 루프 : 이웃 노드들을 방문하고 d[x]를 갱신한다.



두 번째 루프를 마치고 난 뒤의 그래프.

  • 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것(d[B]=10)으로 선택된다. B를 방문하여 S에 추가하고 Q에서 제거한다.

  • B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. d[E] 값이 무한에서 d[B]+(B와 E 사이의 값 = 20) = 30 으로 업데이트된다.


4. 세 번째 루프 : 더 작은 d[x]를 발견한다면?


  • Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문에 방문되는 노드는 D이다.

  • D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트해야 하는데, d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었다. 하지만, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 따라서 d[C]의 값을 30에서 20으로 갱신한다.

  • d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 갱신한다.


5. Q가 공집합이 될 때 까지 루프를 반복한다.

  • S = {A, B, D, C, F, E} (방문한 순서대로 정렬)

  • d[A] = 0

  • d[B] = 10

  • d[C] = 20

  • d[D] = 15

  • d[E] = 30

  • d[F] = 25

  • Q = ∅


알고리즘의 흐름을 보면, 계속 가중치가 작은 간선을 골라 인접한 노드들의 데이터를 갱신해나가는 과정이란 것을 알 수 있다.
따라서 이 알고리즘은, 한 정점에서 다른 정점까지의 최단경로는, 중간에 방문하는 노드들도 최단경로로 방문해야 한다고 주장하는 것이다.

생각해보면 당연하다. A에서 C로 가는 최단경로가 A-(10)->B-(20)->C = 30라고 해보자.
만약 중간 노드인 B까지의 최단경로가 사실은 A-(3)->D-(4)->B = 7라고 한다면, 왜 A에서 C까지 가는데 D를 거치지 않겠는가?
당연히 거치는게 더 짧은 경로다. A-(3)->D-(4)->B->-(20)->C = 27

따라서 최단경로는 최단경로들로 이뤄져있다는 주장은 타당하다.

구현에서의 문제는 없을까? 초창기 이 알고리즘의 시간복잡도는 O(V^2) 였다고 한다.
문제는 Q집합 중에서 d[x]가 가장 작은 원소를 찾아 내는게 공짜가 아닌데 있었다.
지금은 최소-힙으로 Q집합을 유지하면서 O(E * logV)로 줄었다.
최소-힙에 정점은 최대 V^2번 들어가고, (힙의 삽입은 O(logN)) 간선은 E번 봐야 하므로 O(E * log(V^2)) = O(E * logV) 이다.

2. 풀이


최소 힙은 친절히도 <queue> 라이브러리에 priority_queue 를 이용해 쉽게 구현 가능하다.

우선순위 큐의 디폴트는 가장 큰 수를 top에 유지하므로 가중치를 음수화시켜 저장하거나, 큐의 선언에 greater를 쓰면 된다.


문제는 대놓고 다익스트라 알고리즘을 쓰라는 문제로, 시작점은 하나 주어지고 나머지 노드들 까지의 최단경로를 구해야 한다.


이중 벡터로 그래프를 구현하고, 집합 Q는 우선순위 큐로, d[x]는 거리를 저장하는 시퀀스를 선언해 구현해보자.

알고리즘의 구현에 대해 더 깊게 생각해보면, 꼭 INF의 초기화와 계산값을 비교하여 갱신하는 과정이 항상 필요할까?

BFS에서 편했던 점은 방문 노드를 표시하여, 다음 번엔 방문하지 않는 꼼수가 있었는데, 다익스트라는 불가능 할까?


실은 최소 힙을 쓰면서 해결된 의문점이다. 이미 INF에서 갱신된(방문한) 노드는 나중에 다시 경로값을 계산하지 않아도 된다.


무슨 소리냐, 앞에서 노드 C는 갱신하지 않았냐고 의문이 들겠지만,

이는 A의 이웃인 C를 큐에 넣으면서 갱신한데서 비롯되는 문제다. 따라서 큐에서 꺼낼 때만 d[x]를 갱신한다면,

최단경로는 최단경로의 합이란 논리하에 나중에 갱신된 값이 다시 갱신될 일은 없다.



4. 후기


최단경로 문제는 널리고 널렸다. 네이게이셔등의 현실과도 밀접한 알고리즘이기도 하다. 숙지하도록 하자.

다른 최단경로 문제들도 계속 소개하고자 한다.


알고리즘의 그래프 사진들과 설명은 위키백과를 참고하였다.

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


1) 1753 최단경로 : https://www.acmicpc.net/problem/1753

'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 16118 달빛 여우  (0) 2018.10.01
백준) 1753 최단경로  (0) 2017.09.09

+ Recent posts