문제 정의

  • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
    • 밸만 포드 : O(VE)
    • 문제의 유형에 따라서 적합한 알고리즘 선택
    • Floyd를 사용할경우 O(V^3)
    • 다익스트라 : O(ElgE)
      • 음수의 간선 확인 가능
  • 음수로 인한 거리 무한감소 사이클 확인 가능

문제 접근

  • 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)
  • dist배열의 시작 노드값을 0으로 만듬
  • 모든 간선에 대해서, 간선을 지나는 경우 비용이 더 감소할 경우 업데이트
  • 위 과정을 노드의 개수만큼 반복
  • 마지막 한번 모든 간선에 대해서, 위 과정을 반복
    • 이때 비용이 더 감소하는 경우가 있다면 >> 무한 사이클 확인

시간복잡도

  • 모든 간선을 : O(V)
    • 노드의 개수만큼 반복 : O(E)
    • O(V*E)

대표예제 : 백준 11657 타임머신

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
#include <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef long long ll;
 
const int inf = 1e8+10;
 
// 거리배열 생성
ll dist[510];
ti3 edge[6010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(dist, dist+510, inf);
    
    for(int i=0; i<E; i++){
        int a,b,c; cin >> a >>b >> c;
        edge[i] = {a,b,c};
    }
    
    // 시작노드 0으로 초기화
    dist[1] = 0;
    
    // 모든 간선을 노드 갯수만큼 반복
    for(int j=0; j<V; j++) {
        for(int i=0; i<E; i++) {
            int a,b,c; tie(a,b,c) = edge[i];
            
            // 아직 거치지 않은 점일경우
            if(dist[a] == inf) continue;
            // a점을 거친 경우 거리가 더 작아질경우
            if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    
    // 사이클 확인
    for(int i=0; i<E; i++) {
        int a,b,c; tie(a,b,c) = edge[i];
        
        if(dist[a] == inf) continue;
        // a점을 거친 후 거리가 작아질경우 사이클
        if(dist[b] > dist[a] + c) {
            cout << -1 << '\n';
            return 0;
        }
    }
    
    for(int i=2; i<=V; i++) {
        if(dist[i] == inf) cout << -1 << '\n';
        else {
            cout << dist[i] << '\n';
        }
    }
    
    return 0;
}
 
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree, 세그먼트 트리 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

문제링크 : https://www.acmicpc.net/problem/11779


문제 접근

  • 다익스트라 응용문제
  • 다익스트라 개념 참조 : https://dev-jango.tistory.com/26
  • 경로를 구하는 조건이 추가됨 > 이전 경로를 추적하기 위해 pre 배열 사용 : 해당 노드에 도착하기 이전 노드

시간복잡도 계산

  • 다익스트라 시간복잡도 : O(ElgE)
  • 20 * 1e5 = 2e6

인트 계산

  • 거리
    • 거리가 나올수 있는 최대값 = 모든 도시를 최대 비용으로 거치는경우
    • 1000 * e5 = e8 > INT 사용 가능

코드

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
// 이전 노드값
int pre[1010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
                // 이전 노드값 추가
                pre[ni] = ei;
            }
        }
    }
    
    cout << dist[en] << '\n';
    vector<int> path;
    int cur = en;
    while(cur != st) {
        path.push_back(cur);
        cur = pre[cur];
    }
    path.push_back(cur);
    
    cout << path.size() << '\n';
    reverse(path.begin(), path.end());
    for(int x : path) cout << x << ' ';
    
    
    return 0;
}
 
 
cs

문제유형

  • 다익스트라 - 경로
    • pre 배열을 사용해서 경로를 추적

'알고리즘 > 백준' 카테고리의 다른 글

백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP)  (0) 2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP)  (0) 2021.02.14
백준 11780 플로이드2 풀이(C++/CPP)  (0) 2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)  (0) 2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP)  (0) 2021.02.07

문제 정의

  • 문제유형
    • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
      • 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
      • Floyd를 사용할경우 O(V^3)
      • 다익스트라 : O(ElgE)

문제 접근

  • 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)

    • dist배열의 시작 노드값을 0으로 만듬

  • 시작 노드 연결된 간선을 모두 우선순위 큐에 넣음

  • 우선순위 큐가 가지고 있는 가장 작은 간선을 꺼냄

  • 이 간선을 통할경우 기존의 거리 값보다 작아질때, 해당 노드에 연결된 간선을 우선순위 큐에 추가

  • 위 과정을 우선순위 큐가 empty될때까지 반복


시간복잡도

  • 모든 간선을 우선순위 큐에 넣음 : ElgE


대표예제 : 백준 1913 최소비용 구하기

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    cout << dist[en] << '\n';
    
    
    return 0;
}
 
cs

문제 유형

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree, 세그먼트 트리 알고리즘  (0) 2021.02.14
[알고리즘] Bellman Ford, 벨만 포드 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

+ Recent posts

티스토리툴바