문제를 풀다보니까, 유니온-파인드 개념이 어려운게 아니라, 어려운 그리디 문제가 많은것 같다(형식만 유니온-파인드인)

 

일단 개념은 여기, 여기, 여기, 여기, 여기가 배우기 좋다.

교집합이 없는 서로소 집합(Disjoint Set)이라고도 불린다.

union연산과 find연산 단 2개만을 지원하는 자료구조로 disjoint한 집함들을 표현하는 자료구조.

따라서 도로 분할하는건 굉장히 힘들지만 보통 합치는 방향만 필요할때 유용.

이게 표현하려는 집합은 어떤 두 집합 사이에도 교집합 원소가 하나도 없고, 모든 집합의 합집합은 전체집합이라는 뜻.

따라서 파티션과 같다. 기본적으로 set마다 하나의 트리를 이루므로 forest(숲)의 형태를 띈다. (숲 = 트리의 집합)

 

 

근데 굳이 이걸 왜쓰는지가 중요한데,

트리구조 여러개를 다루면서 동적으로 변하는 구조에 대해서는 기존 STL만 가지고 핸들링하기 한계가 있는것 같음

근데 다른 자료구조에 비해 실무적인 연관성이 상당히 떨어져 보이기는 한다.

문제를 위해 꼬으고 꼬은 것처럼 보인달까? 

 

아무튼 disjoint set 마다 트리를 하나씩 가지게 하자는 개념인데..

 

초기화

최초 한 번만 수행되며, N개의 서로 독립적인 트리를 만들어 주는 단계 (모든 노드가 root 노드)

 

Find

Finx(x)는 노드 x의 부모중 루트를 반환하는 연산을 한다. 

disjoint set에서 임의의 두 노드들이 같은 집합에 속해있는지 확인하는 방법은 Find()로 나오는 값이 같은지 보는것.

Find연산의 시간복잡도는 트리의 높이 h에 비례 하므로 경로 압축과정을 통해 넓고 얕게 트리를 유지하는 코드가 들어가게 된다.

 

 

 --> 

이렇게..

 

Union

초기화랑 find만 있으면 당연히 의미가 없고, 같은 set에 포함된 노드들을 합치는 연산이 필요하다. 그게 union이고, 

두개의 트리를 합치는 작업이 들어가는데, 합쳐진 트리의 높이를 낮게 유지하기 위해 작은 트리의 부모를 큰 트리의 root로 하는 작업을 해주게 된다. 이걸 랭크압축이라고 하며, 여기를 참조하자.

 

시간복잡도

union연산의 복잡도도 find연산이 지배함.

find연산은 노드개수 N개, 연산수 M개일때 O(Mlog*N)인데 log*N이 워낙 작은 값이라 O(M)으로 봐도 좋다고 한다.

즉 거의 상수시간에 find, union연산이 되는것

 

 

재활용코드

아래는 내가 처음 짜본 union-find 코드이다. 이 문제의 답안이기도 하다.

경로압축과 랭크압축중 경로압축만 간단하게 되어 있다.(경로압축 안할경우 TLE발생)

코드 작성 자체는 매우 심플하고 구현하기 쉬웠다.

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
int n, m, op, x, y;
int find(int x, vector<int>&parent){
    int ox = x;
    while(parent[x]!=x) x=parent[x];
    parent[ox]=x;  // 여기, 경로압축
    return x;
}
 
void uni(int x, int y, vector<int>&parent){
    int xp = find(x,parent), yp = find(y, parent);
    //임의로 y를 x에 붙여보자.
    parent[yp]=xp;
}
 
int32_t main()
{
    scanf("%d%d", &n,&m);
    vector<int> parent(n+1);REP1(i,n)parent[i]=i;
    REP(i,m){
        scanf("%d%d%d", &op,&x,&y);
        if(op==0){  //union
            uni(x,y,parent);
        }else{  //find
            printf("%s\n", find(x, parent)==find(y, parent)?"YES":"NO");
        }
    }
    return 0;
}
 cs

 

실제 재활용하기에는 아래코드가 더 좋은것 같다(캡슐화되어 있고, 좀더 효율적인 경로압축, 랭크압축 되어 있음)

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
const int INF = (int)1e9;
 
struct union_find{
    vector<int> p,r;
    union_find(int n){
        p.resize(n+1), r.resize(n+1);
        for (int i=0; i<=n; i++) {
            p[i] = i;
        }
    }
    int find(int x){
        if(p[x] == x) return x;
        else return p[x] = find(p[x]);
    }
 
    void uni(int a, int b){
        a = find(a);
        b = find(b);
        if(r[a] < r[b]) p[b] = a;
        else p[a] = b;
        if(r[a] == r[b]) r[a]++;
    }
};
 
int n, m, op, x, y;
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#endif
 
    scanf("%d%d", &n,&m);
    union_find uf(n);
    REP(i,m){
        scanf("%d%d%d", &op,&x,&y);
        if(op==0) uf.uni(x,y);
        else printf("%s\n", uf.find(x)==uf.find(y)?"YES":"NO");
    }
    return 0;
}
 
 cs

 

아래는 uni()함수에서 합쳐진 집합의 크기를 리턴하도록 개선한 버전(내꺼 초기버전 베이스로 만들었다)

이 문제의 답안이기도 하다. 이버전이 랭크압축한거 보다 오히려 왼쪽으로 정렬되는 효과가 있어서 일부문제에서는 더 좋았다.

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
 
struct union_find {
    vector<int> parent, cnt;
    union_find(int n) {
        parent.resize(n + 1), cnt.resize(n + 1);
        REP1(i, n)parent[i] = i, cnt[i] = 1;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }
 
    int uni(int x, int y) {
        int xp = find(x), yp = find(y);
        //임의로 y를 x에 붙여보자.
        if (xp != yp) {
            cnt[xp] += cnt[yp];
            parent[yp] = xp;
        }
        return cnt[xp];  // 합친 집합의 개수를 리턴
    }
};
 
int T, F, ix;
string s1, s2;
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> T; while (T--) {
        cin >> F;
        map<string, int> m; ix = 0;
        union_find uf(2 * F);
        while (F--) {
            cin >> s1 >> s2;
            if (m.count(s1) == 0)m[s1] = ++ix;
            if (m.count(s2) == 0)m[s2] = ++ix;
            cout << uf.uni(m[s1], m[s2]) << '\n';
        }
    }
    return 0;
}
 
 cs

 

 

 

 

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

세그멘트 트리  (0) 2020.04.13
최소신장트리(MST, Minimum Spanning Tree)  (0) 2020.04.12
그래프 최장거리, 최대이득, 최다비용등  (0) 2020.04.09
비트연산  (0) 2020.04.02
사이클 검출(Cycle Detection)  (0) 2020.03.30

최장거리 구하는 문제는 기본적으로 모든 정점을 다 가보고 max값 갱신해주는 형태이다.

백준 10273번 고대동굴탐사 문제처럼 최장거리 뿐 아니라 최대 이득, 최대 비용 이런식으로 비용의 문제로 출제되는 경우도 있다.


한가지 생각할 점은, 모든 정점을 다 가보는 방식이므로 DFS도 효율적이라는 점(BFS를 고집할 필요없다.)

그리고 이문제는 의외로, 방향그래프와 무방향그래프에서의 접근방법이 다른데,

방향그래프에서는 사이클이 없는 DAG이어야 구할 수 있고, 의외로 위상정렬 개념이 들어간다.

위상정렬 개념 없이는 아래와 같은 그래프에서 최장거리 구하기가 까다롭다.

사이클이 존재하는 그래프에서의 최장거리구하기 문제는 NP-Hard에 속하기 때문에PS에서는 안나온다.
모든 정점이 연결되어 있는 완전그래프에서의 최장거리는 TSP문제와 같아진다.

무방향 그래프에서도 당연히 사이클이 없는 트리와 같은 형태로만 PS문제로 주어지고, 이경우는 그냥 BFS같은거 돌리면 된다.
(단순 visit처리만 하면 됨)


사이클없는 무향그래프(트리)에서 최장거리 구하기

기본적으로 트리이거나 포레스트이므로 단순히 BFS돌리면서 max 갱신만 해주면 된다.

이 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
struct node { int v, w; };
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi longest(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi visit(max_v), max_dist(max_v, -1);
    queue<node> q; q.push({ start_v,0 }); visit[start_v] = 1;
    int ln = -1, ld = 0;
    while (q.size()) {
        node n = q.front(); q.pop();
        if (n.w > max_dist[n.v]) max_dist[n.v] = n.w;
        for (node adj : adj_list[n.v]) {
            if (visit[adj.v])continue; visit[adj.v] = 1;
            q.push({ adj.v, adj.w + n.w });
        }
    }
    return max_dist;
}
//최장경로 길이와 해당노드만 리턴
node longest2(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    int ln = -1, ld = 0;
    vi md = longest(max_v, start_v, adj_list, base1);
    for (int i = (int)base1; i < (int)base1 + max_v; i++)
        if (i != start_v && md[i] > ld)ld = md[i], ln = i;
    return { ln,ld };  // longest node, longest distance
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    //일단 인접리스트 받자
    //V:정점개수
    int V; cin >> V;
    vvn adj_list(V + 1);
    for (int i = 0; i < V - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w });
        adj_list[v].push_back({ u, w });
    }
    node n1 = longest2(V, 1, adj_list, true);
    node n2 = longest2(V, n1.v, adj_list, true);
    cout << n2.w << endl;
    return 0;
}
cs

트리의 지름을 구하는 문제의 답안이기도 한데, 

트리의 경우는 임의의 점에서 가장 먼 노드(A)를 찾고 그 노드(A)에서 가장 먼 노드까지의 거리가 트리의 지름입니다. 이 그리디 인사이트만 있으면 풀수있다.


사이클 없는 유향그래프(DAG)에서 최장거리 구하기

이경우 위상정렬을 해야한다(in_edge처리). 이 문제의 답이기도 하다.

또한 이 코드의 경우 모든 경로에 대한 간선개수를 세는 부분도 있으니 참고하자.

보통은 from[N]배열로 단일경로는 찾을 수 있지만, 여기처럼 모든 경로를 찾으려면 max_dist를 이용한 역 탐색이 필요.

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
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi visited(10001), max_dist(10001, -1);  // 간선 카운팅 때문에 밖에 나와있다.
vi longest(int max_v, int start_v, vvn& adj_list, vi& in_edge, bool base1 = false) {
    queue<node> q;
    function<void(node)> enqueue = [&](node n) {
        if (in_edge[n.v] != 0) return;
        q.push(n);
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,0 });
    vi cal(max_v + base1);
    if (start_v == -1)
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = 0, cal[i] = 1;
    else
        max_dist[start_v] = 0, cal[start_v] = 1;
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], adj.w + n.w), cal[adj.v]=1;
            in_edge[adj.v]--;
            enqueue({ adj.v, max_dist[adj.v] });
        }
    }
    return max_dist;
}
 
int32_t main()
{
    int n, m; cin >> n >> m;
    vvn adj_list(n + 1), adj_list2(n + 1);
    vi in(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w }); in[v]++;
        adj_list2[v].push_back({ u, w });
    }
    int s, e; cin >> s >> e;
    vi md = longest(n, s, adj_list, in, true);
    cout << md[e] << endl;
 
    //이제 거꾸로 가면서 간선 개수 카운팅
    set<pair<int, int>> edges;
    queue<node> q; q.push({ e, md[e] });
    vi visited(10001);
    while (q.size()) {
        node n = q.front(); q.pop();
        if (visited[n.v]) continue;
        visited[n.v] = 1;
        if (n.v == s) break;
        for (node adj : adj_list2[n.v]) {
            if (n.w - adj.w == max_dist[adj.v])
                q.push({ adj.v, n.w - adj.w }),
                edges.insert({ min(n.v,adj.v), max(n.v,adj.v) });
        }
    }
    cout << edges.size() << endl;
    return 0;
}
cs


위의 코드를 한층 더 업그레이드(?)해서.. 간선가중치 뿐 아니라 정점가중치도 고려하고, 경로도 구해주는 버전을 만들었다.

이 문제의 답안이기도 하다. 단, 문제특성상 아래코드는 간선가중치는 작을수록 좋고, 정점코스트는 클수록 좋음에 주의

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 <bits/stdc++.h>
using namespace std;
 
const int INF = (int)1e9;
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//간선가중치(adj_list)뿐 아니라 정점가중치(cost)도 같이 고려.
//모든 노드로의 longest 한번에 구하기, 최장거리와 경로도 같이 리턴해준다.
struct result { vi max_dist; int max_value; vi path; };
result longest(int max_v,int start_v,vvn& adj_list,vi& in_edge,vi& cost,int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF), from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0) return false;
        q.push(n);
        return true;
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    vi cal(max_v + base1);
    if (start_v == -1) 
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i], cal[i] = 1; 
    else 
        max_dist[start_v] = cost[start_v], cal[start_v] = 1; 
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], cost[adj.v] - adj.w + n.w),
                cal[adj.v] = 1;
            in_edge[adj.v]--;
            if (enqueue({ adj.v, max_dist[adj.v] })) from[adj.v] = n.v;
        }
    }
 
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
 
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T; while (T--) {
        int N, E; cin >> N >> E;
        vi cost(N + 1); for (int i = 1; i <= N; i++) { cin >> cost[i]; }
        vector<vector<node>> adj_list(N + 1);
        vi in(N + 1);
        for (int i = 0; i < E; i++) {
            int u, v, w; cin >> u >> v >> w;
            adj_list[u].push_back({ v, w }); in[v]++;
        }
        result r = longest(N, 1, adj_list, in, cost, true);
        cout << r.max_value << ' ' << (int)(r.path).size() << '\n';;
        for (auto a : r.path) cout << a << ' ';
        cout << endl;
    }
    return 0;
}
cs



반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

최소신장트리(MST, Minimum Spanning Tree)  (0) 2020.04.12
유니온 파인드(Union-Find), 서로소 집합(Disjoint Set)  (0) 2020.04.10
비트연산  (0) 2020.04.02
사이클 검출(Cycle Detection)  (0) 2020.03.30
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28

이 문제에서 연습할 수 있다.

아래 소스는 위 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main() {
    int S = 0;
    int M; scanf("%d", &M); while (M--) {
        char a[10]; int b; scanf("%s", a);
 
        string s = a;
        if (s == "add") scanf("%d", &b), S |= (1 << (b - 1));
        if (s == "check") scanf("%d", &b), printf("%d\n", S & (1 << (b - 1)) ? 1 : 0);
        if (s == "remove") scanf("%d", &b), S &= ~(1 << (b - 1));
        if (s == "toggle") scanf("%d", &b), S ^= (1 << (b - 1));
        if (s == "all") S = 0 - 1;
        if (s == "empty") S = 0;
    }
    return 0;
}
cs

조금 까리하건 remove와 toggle인데 생각해내기 어렵진 않다.



반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

유니온 파인드(Union-Find), 서로소 집합(Disjoint Set)  (0) 2020.04.10
그래프 최장거리, 최대이득, 최다비용등  (0) 2020.04.09
사이클 검출(Cycle Detection)  (0) 2020.03.30
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27

DFS를 이용한 방법

DFS를 사용한 사이클 검증법은 보통 $O(V)$로 이야기 되는 것 같다. 만약 간선이 많다고 하더라도 V번 안에 back edge가 발견돼서 끝나서 그런듯. (끝까지 사이클이 없는 경우에 최대 V정점, 최대 V간선을 방문하니 2V라서 $O(V)$가 맞긴한듯)

 

back edge를 발견하면 사이클이 있다고 판단하는건데, 순회와 백엣지 개념은 여기가 설명 잘되어 있다.

 

코드는 여기가 좋은 것 같긴한데.. 문제는 딱맞는 샘플문제가 없어서 해보지 못했다

 

여기에 샘플문제가 있고 제출도 가능한것 같아서 해보는 중.

 

DFS로 직접 한 번 구현해보니까, visit배열만 있어도 판단이 되는데, visit를 1로했다 0으로 했다하는 테크닉이 필요했다.아래 cache는 나중에 추가했는데.. 저거 없어도 위에 샘플이 돌긴하는데 TLE가 나길래 추가했고, 추가한 후에 AC떴다.

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
#include <bits/stdc++.h>
using namespace std;
 
 
int V, E, u, v, w, in[101][101], visited[101], cache[101];
 
int DFS_has_cycle(int cur_v) {
    if (cache[cur_v] != INT_MAX) return cache[cur_v];
    visited[cur_v] = 1;
    for (int i = 0; i < V; i++) {
        if (in[cur_v][i]){
            if (visited[i]) return cache[cur_v] = 1;  //back-edge발견, 사이클!
            if (DFS_has_cycle(i)) return cache[cur_v] = 1;
        }
    }
    visited[cur_v] = 0;  // 이부분이 중요(back track한다음에는 0으로 만들어줘야 트리구조로 들어간다.)
    return cache[cur_v] = 0;
}
 
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d", &V, &E);
    fill(&in[0][0], &in[V][V], 0);
    for (int i = 0; i < E; i++) {
        scanf("%d%d", &u, &v);
        in[u][v] = 1;
    }
    
    bool ans = false;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < 101; j++)visited[j]=0, cache[j]=INT_MAX;
        if (DFS_has_cycle(i)) { ans = true; break; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}
 
 cs

근데, 내가 다른사람하고 같은 방식으로 짰는지는 잘 모르겠다;; 

뭔가 여러가지 방식이 있는 느낌이라 좀 헷갈린다.

 

나중에 다른 문제를 풀다가 위의 구현을 썼더니 TLE가 나서 아래 구현으로 바꿨더니 통과했다; 아직 위의 구현에 어떤 문제땜에 느린지 파악은 못함

음 파악해 봤는데.. 위에서 매번 visited, cache 초기화 해주는게 O(N)이다 보니 모든 노드에 대해서 DFS_has_cycle()부르면 O(N^2)이상이 될 수 있는게 문제였다 ㄷ. 아래 소스는 cache는 아예 안쓰고, visited도 한번만 초기화해주면 되다보니 빨랐던것

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
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
 
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(int)> dfs = [&](int cur_v) -> bool {
        if (visited[cur_v]) {
            if (visited[cur_v] == -1) return true;
            return false;
        }
        visited[cur_v] = -1;
        for (int adj : adj_list[cur_v]) {
            if (dfs(adj)) {
                return true;
            }
        }
        visited[cur_v] = 1;
        return false;
    };
    return dfs(cur_v);
}
 
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<int>> adj_list(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        adj_list[u].push_back(v);
    }
 
    bool ans = false;
    for (int i = 0; i < N; i++) {
        if (has_cycle(N, i, adj_list)) { ans = true; break; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}
 cs

 

 

그리고 이게또 direct냐 undirect에 따라서도 다른거 같다.(위는 direct 버전)

 

undirect 버전

undirect는 양방향으로 간선을 처리해준다음에, 트리 순회처럼 parent-child관계로 탐색해 나가고, 

바로전(justbefore)으로 돌아가는 간선은 무시해주는 식으로 처리하면 된다.

이 문제를 통해서 볼 수 있고, 완전한 코드는 아니지만, 아래 코드 참조하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using vi = vector<int>;
using vvi = vector<vi>;
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(int, int)> DFS = [&](int curr, int justbefore) -> bool {
        visited[curr] = true;
 
        for (auto child : adj_list[curr]) {
            if (child == justbefore) continue;
            // cycle 이 생기면
            if (visited[child]) return false;
            if (DFS(child, curr) == false) return false;
        }
        return true;
    };
    return DFS(cur_v, -1);
}
 cs

 

 

그리고 사이클 존재 여부만 판단하느냐, 최소사이클수 같은걸 판단하느냐도 다른듯

최소사이클의 경우는 DFS만으로 커팅하면서 빠르게 판단하기 힘든게 아닌가 생각중

(최소 사이클 나오면 Floyd-Warshall Algorithm이 현재 내가아는한에서는 답이다)

 

 

유니온파인드를 통한 디텍션

undirected의 경우 이 문제의 경우처럼 유니온파인드로도 사이클 디텍션을 할 수 있다.

좀 더 구체적으로는 새로운 간선을 union할 때, 양쪽 정점이 이미 같은 parent를 가지고 있으면, 사이클로 판정가능하다. (중복 간선은 없다는 가정하에, 이미 연결되어 있는데 부가적인 연결이 생기는거라)

간선이 추가되면서 특정 간선이 추가될때 사이클이 완성됨을 판정할때는 dfs보다 유리한 것 같다.

다음은 내 구현이다. 위 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct union_find {
    vector<int> p, r;
    union_find(int n) {
        p.resize(n + 1), r.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
        }
    }
    int find(int x) {
        if (p[x] == x) return x;
        else return p[x] = find(p[x]);
    }
 
    void uni(int a, int b) {
        a = find(a);
        b = find(b);
        if (r[a] < r[b]) p[b] = a;
        else p[a] = b;
        if (r[a] == r[b]) r[a]++;
    }
};
int32_t main()
{
    int n, m; scanf("%d%d", &n, &m);
    union_find uf(n);
    REP(i, m) {
        int u, v; scanf("%d%d", &u, &v);
        if (uf.find(u) == uf.find(v)) {
            printf("%d\n", i + 1);
            return 0;
        }
        else {
            uf.uni(u, v);
        }
    }
    printf("0\n");
    return 0;
}
 
 cs

 

 

트리 디텍션과도 일맥상통.

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

그래프 최장거리, 최대이득, 최다비용등  (0) 2020.04.09
비트연산  (0) 2020.04.02
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27

내용을 대략적으로 이해하기에는 여기가 좋다. (구현방법도 단계별로 익히기 좋..다고 생각했는데 다시 읽어보니 왜 항상 최단이 되는지 why에 대한 설명이 좀 부족한 느낌이 드네.. 아래 증명란에서 추가 검토하자)

 

플로이드와샬의 시간복잡도는 심플하게 $O(V^3)$이다. 

N이 2000일때 TLE난적이 있으니 참고하자. 

($2000^3 = 2,000,000,000$, 20억 정도니 2~20초 걸리는거니 당연할지도)

 

PS에서 쓰는 내 소스코드는 다음과 같다.

(백준 11404번 문제의 답안이기도 하다.)

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
#include <bits/stdc++.h>
using namespace std;
 
//플로이드 와샬
int n, m, u, v, w, in[101][101];
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d", &n, &m);
    //인접행렬만들자
    fill(&in[0][0], &in[n][n], INF);  // 없는간선은 INF
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1] = min(in[u - 1][v - 1], w);
    }
    //정점 i > k > j, 핵심로직
    for (int k = 0; k < n; k++)  // 중간정점을 중심으로, 모든 중간정점을 검토함에 주의
    for (int i = 0; i < n; i++)  // 모든 시작정점
    for (int j = 0; j < n; j++)  // 모든 끝정점
        if (in[i][j] > in[i][k] + in[k][j])  // 현재 최단거리보다 K를 거치는게 더 짧으면
            in[i][j] = in[i][k] + in[k][j];  // 업데이트
 
   //결과출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            // 경로를 못찾았을때 이문제는0으로 바꾸는데, 문제에 따른처리 필요
            printf("%d ", in[i][j] < INF ? in[i][j] : 0);
        printf("\n");
    }
    return 0;
}
 cs

 

 

아래는 주석제거하고 짧은버전

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, w, in[101][101];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if(i-j)in[i][j] = 1e9;
    while(m--) scanf("%d%d%d", &u, &v, &w), in[u-1][v-1] = min(in[u-1][v-1], w);
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        in[i][j] = min(in[i][j], in[i][k] + in[k][j]);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%d ", in[i][j] < 1e9 ? in[i][j] : 0);  
        printf("\n");
    }
    return 0;
}
 
 cs
 
 

경로를 출력하는 문제에 대해서는, 여기를 참조하면 어렵지 않게 구현하고 풀 수 있다.

 

증명

많은 인터넷 상의 자료들은 증명에는 별로 관심없고, HOW에만 관심이 있는듯 보인다.

일단 증명에 대한 힌트는 그래도 위키피디아 여기에서 엿볼 수 있는데..

최대 $(|V|^{2})$의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 

라는 표현이 있는데, 일견 이해는 되지만, 모든 변의 조합을 1회만 업데이트 하면 옵티멀이 된다는게 뭔가 찜찜하다.

여기에 증명이 나와있는데, 설명이 잘 이해가 안된다. 이 동영상이 그나마 쉽게 접근하고 있는데, 여전히 multiple update가 필요하지 않은 이유에 대해서는 설명이 잘 안된다.

 

어쨌거나, 실제 증명은 다음과 같이 귀납법으로 간단하게 정의된다.

$$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\
w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)}, 
\end{cases}$$

 

직관적으로는.. k가 0에서 k가 1로 넘어갈때는 확실한데, k가 1에서 2 이상으로 넘어갈때, 기존 업데이트 된 값들이 최대 k번의 연산 이상으로 업데이트가 필요없다는게 잘 이해가 안된다.

 

 

정점 가중치

이 문제를 보면 간선 가중치 뿐 아니라 정점 가중치도 고려해야하는데, 풀어보면 특별히 난이도가 올라가거나 복잡해지진 않았다.

이문제만 그런걸수도 있긴한데, 현재 발견된걸로 그러함.

 

 

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

비트연산  (0) 2020.04.02
사이클 검출(Cycle Detection)  (0) 2020.03.30
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27

SPFA알고리즘은 벨만포드 알고리즘의 개선판으로, 

벨만-포드 알고리즘이 정점의 개수가 V일때, 모든 정점을 V-1번 갱신하는데 비해, 

SPFA는 queue를 사용해서, 시작점과 연관있는 정점만 갱신해 나가는 아이디어

 

아래는 직접 구현해 본건데 백준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
#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
vector<int> SPFA(int max_v, int start_v, vector<vector<node>>&adj_list) {
    vector<int> min_dist(max_v + 1, INF);
    min_dist[start_v] = 0;
    queue<node> q; q.push({ start_v,0 });
    queue<int> qn; qn.push(0);
    while (q.size()) {
        node n = q.front(); q.pop();
        int nn = qn.front(); qn.pop();
        if (nn >= max_v) { printf("-1\n"); exit(0); }//네거티브 사이클
 
        //이 부분, 아래 for문 안쪽이랑 중복같기도 해보이지만 없으면 TLE난다.
        if (min_dist[n.v] < n.w) continue;
        min_dist[n.v] = n.w;
 
        for (node adj : adj_list[n.v]) {
            //최소값으로 업데이트
            if (min_dist[adj.v] <= adj.w + n.w) continue;
            min_dist[adj.v] = adj.w + n.w;
            q.push({ adj.v, adj.w + n.w }), qn.push(nn + 1);
        }
    }
    return min_dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = SPFA(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}
 cs

 

근데 제출해본 결과, 스피드업이 없었다는 문제가? 복잡도로는 벨만포드와 같기도 하고...

근데 보면 볼수록 신기한점은 우선순위큐만 없고, for문안에 continue로직이 추가됐을뿐이지 다익스트라랑 소스코드가 거의 동일하다는 점이다.

그래도 네거티브 사이클을 디텍트할 수 있는건 장점

 

ChatGPT 말로는 위 코드는 SPFA는 아니라는데 ㅋㅋ 나중에 시간날때 검토해보자.

is it SPFA?
No, it is not SPFA (Shortest Path Faster Algorithm). SPFA is also a single-source shortest path algorithm, similar to Bellman-Ford, but it uses a queue to keep track of the current node and its distance from the starting node, whereas Bellman-Ford uses a simple loop. The implementation you provided is the Bellman-Ford algorithm, as it uses queue, it does not check negative-weighted edges and it uses for loop, which is the characteristic of Bellman-Ford algorithm, also it uses the continue in order to check whether the current node is visited or not, which is another characteristic of Bellman-Ford algorithm.
반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

사이클 검출(Cycle Detection)  (0) 2020.03.30
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19

여기 설명이 워낙 좋아서 한 번 보면 이해되고, 그렇게 어려운 알고리즘도 아니다.


다익스트라와 비슷하게, 하나의 정점에서 다른 모든정점으로의 최단거리를 한번에 구해주지만, 

약간은 느린편이고, 

대신 negative edge에 대해서도 처리가 가능하다.


PS용으로 내가 사용하는 코드는 다음과 같다.

(백준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
#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
 
vector<int> bellman_ford(int max_v, int start_v, vector<vector<node>>&adj_list) {
    //모든 정점의 최단 경로를 무한대로 초기화
    vector<int> dist(max_v+1, INF);
    //시작정점만 0으로 초기화
    dist[start_v] = 0;
    for (int t = 0; t < max_v - 1; t++) {//N-1번 업데이트 수행
        for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
            for (node adj : adj_list[j]) {
                //무한대가 아니면
                if (dist[j] == INF) continue;
                //최소값으로 업데이트
                dist[adj.v] = min(dist[adj.v], dist[j] + adj.w);
                int sfsd = 1;
            }
        }
    }
    //한번더 업데이트 시도해서
    for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
        for (node adj : adj_list[j]) {
            if (dist[j] == INF) continue;  // 고립된건 무한대일수 있음
            //업데이트가 일어나면
            if (dist[adj.v] > dist[j] + adj.w) {
                //네거티브 사이클이 있는것
                printf("-1\n"); exit(0); // 코드 재활용시 이부분 주의
            }
        }
    }
    return dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = bellman_ford(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}
cs


시간복잡도

복잡도는 정점의 개수가 $V$ 이고 간선의 개수가 $E$일때 $O(VE)$가 되며,

directed graph기준으로 모든 정점간 간선이 꽉차있다고 하면 $E = (V-1)^2$이 되어 $O(V^3)$이 된다.

근데 보통 간선이 꽉차있지 않고, undirected라고 하더라도 간선의 개수가 sparse 하지만 않다면, 

복잡도로 치면 $O(E) = O(V^2)$이 되는 경우가 일반적이라서 전체적인 벨만포드의 복잡도는 $O(V^3)$정도로 보면 된다.(다익스트라가 $O(V^2)$미만으로 계산되는데 비해서 비싼편)


반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19

최단거리를 구할때 BFS를 쓰는 경우가 많은데,


만약 정점 간 거리가 일정하지 않다면, 다익스트라를 쓰면된다 (BFS와 기본로직은 비슷하다)


다익스트라는 시작 정점에서 다른 모든 정점으로의 최단거리를 한 번에 구할 수 있다.

(모든 정점에서 다른 모든 정점은 아닌것에 주의, 이걸 원한다면 플로이드 와샬 알고리즘을 써야한다)


주의할점은 정점간 거리에 음수가 있으면 안된다는 점이다.(negative edge)

이때는 벨만-포드 알고리즘을 써야한다.


근데, negative edge가 안되는 버전이 가장빠르고, 하나의 정점을 두번이상 방문하지 않기는 하는데,

> enqueue, dequeue는 여러번 되는데 첫번째 dequeue만 효과를 가지고 나머지는 무시된다는걸 이해하는게 중요하다. visit 배열을 사용해서 두번째 이후 dequeue를 강제로 무시해도 OK. 무시되지 않는 dequeue를 "방문"이라고 생각하면 하나의 정점을 한 번만 방문하는게 맞다. enqueue/dequeue는 오히려 간선관점에서 O(E)안에 포함된다고 보는게 맞을거 같다.

하나의 정점을 여러번 방문할 수 있게 허용하면 negative edge를 가지는 경우에도 쓸 수 있다.

아래 내 소스에서 min_dist[n.v] != INF 이부분을 min_dist[n.v] < n.w 이렇게 바꾸면, 여러번 방문할 수 있게 허용하는 버전이 된다.

이 답변에서 3번 variant가 되는 것

근데 사실 이렇게 재방문을 허용하게 되면 다익스트라만의 complexity 장점이 사라지는 셈이라,

SPFA를 쓰는게 더 좋은경우가 생기는걸 보았다.

실제로 발생하면 SPFA쪽을 사용하자.


내가 작성한 PS에서 사용하는 다익스트라 로직은 다음과 같다.

(백준 1753 문제의 답안이기도 하다)

근데 여기에 따르면 아래구현은 이미 방문한 정점을 다시 방문시 TLE로 만들 수 있으며

q.pop()한다음에 if(n.w > min_dist[n.v]) continue; 이 코드를 넣어줘야 한다고 한다. 나중에 체크해보자.

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
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
bool operator<(node l, node r) { if (l.w == r.w)return l.v > r.v; return l.w > r.w; }
using vi = vector<int>;
using vvn = vector<vector<node>>;
const int INF = INT_MAX / 4;
vi Dijkstra(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi min_dist(max_v, INF);  // 거리 무한대로 초기화
    priority_queue<node> q;
    q.push({ start_v, 0 });  // 거리 0으로 시작정점 enqueue
    min_dist[start_v] = 0;   // 시작점 스스로의 거리는 0 (문제에 따라 중요한 경우 있음)
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            // min_dist를 통한 visit 처리(enqueue하기 전에 visit처리해주는게 중요하다)
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w });
            }
        }
    }
    return min_dist;
}
 
int main()
{
    //V:정점개수, E:간선개수, K:시작점
    int V, E, K; scanf("%d%d%d", &V, &E, &K);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    vector<int> d = Dijkstra(V, K, adj_list, true);
    for (int i = 1; i <= V; i++)
        if (d[i] == INF)puts("INF");
        else printf("%d\n", d[i]);
    return 0;
}
cs




Tip1

최단거리 이외에 비용등의 추가 constraint가 붙을 경우 min_dist가 현재 1차원 배열인데 2차원으로 차원을 늘리면 풀릴 수 있다. (백준 10217번이 그 예)

참고로 위 소스에서 min_dist는 int min_dist[max_v + 1]; 로 해도 되지만 max_v가 상수가 아닌 변수여서 vector로 해놓은건데,

차원이 늘어나서 int min_dist[max_v + 1][M + 1]; 과 같은 형태가 된다면 vector of vector가 필요하다. 

이때는 약간 복잡해보일수는 있으나, 다음과 같이 코딩하면 된다.

1
2
    vector<vector<int>> min_dist(max_v + 1, vector<int>(M+1, INF));
 
cs


최대값을 상수값으로 적는대신 변수값으로 가변적으로 세팅할 수 있는 장점(이때문에 문제마다 최대값에 따라 101, 2001등 수정할 필요가 없어진다) 이외에, 덤으로 초기값을 INF로 별도 loop없이 편하게 줄 수 있는 장점도 있다.


경로추적

경로추적이 필요한 경우에는 아래 소스처럼 from 배열을 하나 운영하면 된다. 이 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
struct node { int v, w; };
bool operator<(node l, node r){if(l.w==r.w)return l.v>r.v; return l.w>r.w;}
int n, m, s, e;
typedef vector<vector<node>> vvn;
typedef vector<int> vi;
vector<int> Dijkstra(int max_v, int start_v, vvn& adj_list, vi& from) {
    vector<int> min_dist(max_v + 1, INF);
    priority_queue<node> q;
    q.push({ start_v, 0 });
    min_dist[start_v] = 0;
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w }), from[adj.v] = n.v;  // 경로 기록
            }
        }
    }
    return min_dist;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    vvn adj_list(n + 1);
    vi from(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    scanf("%d%d", &s, &e);
    vi d = Dijkstra(n, s, adj_list, from);
    printf("%d\n", d[e]);
    if (s == e) {
        printf("1\n%d\n", s);
        return 0;
    }
    deque<int> dq;
    while (e != s && from[e] != -1)dq.push_front(e), e = from[e];
    dq.push_front(s);
    printf("%d\n", dq.size());
    for (auto a : dq)printf("%d ", a); puts("");
 
    return 0;
}
cs




복잡도

BFS의 복잡도가 $O(E+V)$ 인데 반해서 다익스트라의 복잡도는 $O((V+E)\times log(V))$이다. 왜 다익스트라가 더 높냐구? 다익스트라는 BFS와 다르게 간선거리를 고려해야하므로, priority queue를 써야하고 그에 따라 $log(V)$가 추가되는 것.BFS는 그냥 queue를 쓰므로 $O(1)$. 

보통은 아무리 sparse해도 정점이 간선보다 많은 경우는 문제로 잘 안주어진다 따라서 $E >= V$인 경우가 대부분이고 이렇게 되면 복잡도가 $O(E \times log(V))$이다. 이것 때문에 다익스트라 복잡도를 보통 이걸로 얘기하는 것. 트리의 경우는 $E=V-1$이지만, dense한 그래프의 경우 $E \sim V^2$이므로 이 경우는 $O(V^2log(V))$정도로 심플하게 봐도 좋다. 


반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09

DFS는 탐색기법의 하나로, 트리인 경우 아래처럼 말단 노드까지 쭉 내려가본 다음, 다시 올라오면서(back track) 안가본 노드를 가보는 식으로 동작한다.


동작기법이 재귀호출과 유사하여, 재귀로 많이 구현하는 편


재귀를 사용하는 경우 시스템 스택의 제한을 받아서 탐색공간이 너무 크면 stack overflow가 발생할 수 있는 단점이 있다.


시간복잡도

V개의 정점, E개의 간선으로 이루어진 그래프의 경우에..

여기에 잘 나와있는데, 인접행렬로 구현했을 경우 다음 간선으로 가는데 V루프를 돌리므로, 시간복잡도는 $O(V^2)$이 되고(E에 상관없음에 주의),

인접리스트로 구현할 경우 랜덤액세스 형식으로 다음 간선으로 접근하므로 $O(V+E)$가 된다. (근데 간선이 굉장히 많은 경우는 $E \sim V^2$개 근처까지 가므로 이때는 $O(V+V^2) = O(V^2)$ 이렇게 되기는 한다.)

그래서 인접리스트로 구현하는게 인접행렬보다 좋은 어프로치다.





반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09
냅색DP(knapsack DP)  (0) 2020.03.07


너비우선탐색(BFS)는 다음처럼 물결이 퍼지듯 가까운 경로 후보부터 탐색하는 방법이다

한쪽 길을 끝까지 먼저 탐색하는 깊이우선탐색(DFS)과 비교된다



이런걸 왜쓰냐면 

1 최단경로를 구할때, 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있어 DFS에 비해 빠른경우가 많고

2 보통 재귀를 통해 시스템스택을 사용하는 DFS에 비해 queue를 사용하기 때문에 스택오버플로에서 비교적 자유롭고 힙공간을 넓게 쓸 수 있어 좀 더 넓은 범위 탐색에 유리하다.


S에서 E로 최단경로를 참색하는 아래 예제를 보자



시간복잡도

DFS와 마찬가지로 BFS도 인접행렬로 구현하면 $O(V^2)$이고 인접리스트로 구현하면 $O(V+E)$인것 같다. 
조금 헷갈리는건 간선이 많아도 결국 V개 노드만 방문하는데 O(E)가 어디서 소모되는지?.. 어쨌든 visted 정도라도 체크하니까 그런것일까? ㅎ

경로찍기 & 람다(lambda)함수 사용

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
#include <bits/stdc++.h>
using namespace std;
int N, K, x, c, visit[100001], from[100001];
deque<int> seq;
int main(void) {
    fill(from, from + 100001, -1);
    scanf("%d%d", &N, &K);
    queue<int> qx, qc;     qx.push(N), qc.push(0);
    while (qx.size()) {
        x = qx.front(); qx.pop();
        c = qc.front(); qc.pop();
        if (x == K) {
            printf("%d\n", c); break;
        }
        auto enqueue = [&](int v) {
            if (v <= 100000 && v >= 0 && visit[v] == 0) 
                visit[v] = 1, qx.push(v), qc.push(c + 1), from[v] = x;
        };
        enqueue(2 * x);
        enqueue(x - 1);
        enqueue(x + 1);
    }
    for (int i = 0; i <= c; i++) seq.push_front(K), K = from[K]; 
    for (auto a : seq)printf("%d ", a); printf("\n");
    return 0;
 }
cs

최단거리 뿐 아니라 그 경로도 찍고 싶다면 위처럼 글로벌하게 from배열을 하나 운용하면 된다.

람다함수 사용도 잘 봐두자. 위 코드는 이 문제에 대한 답안이기도 하다.

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09
냅색DP(knapsack DP)  (0) 2020.03.07
이진탐색/이분탐색 (Binary Search) 알고리즘  (0) 2019.12.09

+ Recent posts

티스토리툴바