최종 순위




기존 위상이 주어지고, 노드끼리의 위상을 뒤바꿨을 때, 새롭게 위상들이 잘 정렬되는지 확인해야 하는 문제다.

따라서 그래프를 잘 정의해서 위상이 뒤바뀜을 잘 데이터로 표현해야 한다.


위상이 뒤바뀌면 그래프에선 무슨 일이 생길까?

주의할 점은 두 노드끼리의 위상순서만 바꾸는 것이지, 다른 노드들와의 위상순서는 그대로야 한다는 점이다.


첫번째 테스트 케이스를 보면 위상순서는 5 < 4 < 3 < 2 < 1 이다.

이후 2와 4 // 3과 4의 위상순서를 바꾸라고 한다.

기존의 위상비교는 2 > 4 // 3 > 4 였으니, 2 < 4 // 3 < 4로 바꿔야 한다.

이 때 기존의 위상비교, 예를 들어 5 < 4 나 3 < 1 같은 순서는 바뀌면 안되는 것이다.


그래프에선 간선만 휘까닥 뒤집어주면 된다. 애초에 a->b로 진출하는 간선이었다면,

이는 명확히 위상순서가 a<b임을 나타내고 있다.

따라서 간선만 a<-b로 바꿔주면 기존의 위상순서를 지키면서 바꿔줄 수 있다.


이제 그래프를 무엇으로 표현할지 생각해보자.

인접리스트로 표현한 그래프라면 뒤집어야 할 해당간선을 찾는데 해당 리스트를 전부 뒤져야 한다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 그냥 리스트 전부를 보면 되는데 간편함이 있다.


반면 인접행렬로 표현한 그래프라면 뒤집어야 할 해당간선을 바로 찾을 수 있음에 이점이 있다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 해당 행을 전부 봐야하는데 단점이 있다.


큐질에서 어차피 둘 다 O(n)이므로 인접행렬로 하자.

주의할 점은 기존 순위로 간선을 만들 때에, 5->4->3->2->1로 간선 4개만 만드는게 아니라,

5->4, 5->3, 5->2, 5->1
4->3, 4->2, 4->1
3->2, 3->1,
2->1

모든 간선을 만들어줘야 한다는 점이다. 이래야 나중에 간선을 뒤집을 때에 기존 위상순서를 유지할 수 있다.


정답은 세 가지로 분류되는데, 확실한 순위가 정해지든지(1), 순위가 안정해지든지(2), 데이터에 일관성이 없든지(3) 세 가지다.

(1)은 위상정렬이 완료되면 당연한 결과다.

(2)는 테크트리가 완료되는 노드가 동시에 2개 이상 생긴다는 뜻으로, 큐에 2개 이상의 노드가 들어가는 결과다.

(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
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
 
int tc, n, m, a, b;
int mat[501][501], order[501], in[501];
 
int main() {
    scanf("%d"&tc);
    while (tc--) {
        memset(mat, 0sizeof(mat));
        memset(in, 0sizeof(in));
 
        scanf("%d"&n);
        for (int i = 1; i <= n; ++i)
            scanf("%d"&order[i]);
 
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                mat[order[i]][order[j]] = 1;
                in[order[j]]++;
            }
        }
 
        scanf("%d"&m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d"&a, &b);
            if (mat[a][b]) {
                mat[a][b] = 0;
                mat[b][a] = 1;
                in[b]--, in[a]++;
            }
            else {
                mat[b][a] = 0;
                mat[a][b] = 1;
                in[a]--, in[b]++;
            }
        }
 
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (!in[i])
                q.push(i);
 
        bool certain = true;
        vector<int> ans;
        while (!q.empty()) {
            if (q.size() > 1) {
                certain = false;
                break;
            }
 
            int cur = q.front();
            q.pop();
            ans.push_back(cur);
 
            for (int next = 1; next <= n; ++next) {
                if (mat[cur][next]) {
                    in[next]--;
                    if (!in[next])
                        q.push(next);
                }
            }
        }
 
        if (!certain) //uncertain
            puts("?");
        else if (ans.size() == n) { //possible
            for (int i = 0; i < n; ++i)
                printf("%d ", ans[i]);
            puts("");
        }
        else //impossible
            puts("IMPOSSIBLE");
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

장난감조립




완제품을 조립하기위해 기본 부품들과 기본 부품들로 만드는 중간 부품들이 필요하다.

기본->중간 // 중간->중간 // 중간->완제품 으로 만들기 위해 필요한 개수가 주어질 때,

완제품을 만들기 위해 필요한 기본 부품들의 갯수를 구해보자.


테크트리를 탄다는 점에서 위상정렬을 생각해 볼 수 있다.

또한 부품을 여러개 써야 다음 단계로 넘어갈 수 있다는 점에서, 간선에 그 몇개에 해당하는 정보도 저장해야 한다.

그리으로 나타내면 다음과 같다.


간선을 잘 정의해서 그래프를 구성하자.

또한 각 노드마다 어떤 기본 부품이 몇개 필요한지 저장할 배열도 필요하다.

기본 부품은 진입차수가 0인 노드임을 금방 알 수 있다. 기본 부품들의 부품배열엔 자기 자신만 들어가 있을 것이다.


이제 위상정렬을 위한 큐질을 하면서 노드의 부품배열에 간선의 가중치를 전부 곱해서 다음 노드의 부품배열에 더해주자.

이후 간선을 제거해가면서 진입차수가 0이 된다면 부품이 완성된 것이고, 다음 단계로 넘어갈 수 있다. 큐에 넣는다.

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 <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct edge {
    int num, val;
};
int blocks[101][101];
int in[101];
int n, m, x, y, k;
 
int main() {
    scanf("%d %d"&n, &m);
    vector<vector<edge>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d"&x, &y, &k);
        vec[y].push_back({ x,k });
        in[x]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i]) {
            q.push(i);
            blocks[i][i] = 1;
        }
    }
        
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (auto next : vec[cur]) {
            for (int i = 1; i <= n; ++i)
                blocks[next.num][i] += blocks[cur][i] * next.val;
 
            in[next.num]--;
            if (!in[next.num])
                q.push(next.num);
        }
    }
 
    for (int i = 1; i <= n; ++i)
        if (blocks[n][i])
            printf("%d %d\n", i, blocks[n][i]);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

Strahler 순서




위상정렬의 변형문제.

strachler 순서가 정해지는 데 일련의 규칙이 있고, 따라서 간선을 지울 때 다른 작업을 추가로 해줘야 한다.


먼저 진입차수가 0인 노드들의 strachler 순서는 0이다. 이제 이 노드들이 큐에서 꺼내질 때, 노드의 진출 간선들을 지우면서

규칙에 따른 작업을 한다.


규칙은 다음과 같다.

  • 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.


그래서 각 노드는 순서값, 들어오는 강의 순서들, 가장 큰 값을 기억해야 한다.


이후에는 규칙대로 풀면 된다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct Strahler {
    int max, order_cnt[1001], order;
};
 
int in[1001];
int k, kk, m, p, a, b;
 
int main() {
    scanf("%d"&k);
    while (k--) {
        scanf("%d %d %d"&kk, &m, &p);
        for (int i = 1; i <= m; ++i)
            in[i] = 0;
 
        vector<vector<int>> vec(m + 1);
        for (int i = 0; i < p; ++i) {
            scanf("%d %d"&a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
        vector<Strahler> st(m + 1);
        queue<int> q;
        for (int i = 1; i <= m; ++i) {
            if (!in[i]) {
                q.push(i);
                st[i].order = 1;
            }
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (auto next : vec[cur]) {
                if (st[next].max < st[cur].order)
                    st[next].max = st[cur].order;
 
                st[next].order_cnt[st[cur].order]++;
 
                in[next]--;
                if (!in[next]) {
                    if (st[next].order_cnt[st[next].max] == 1)
                        st[next].order = st[next].max;
                    else if (st[next].order_cnt[st[next].max] > 1)
                        st[next].order = st[next].max + 1;
                    q.push(next);
                }
            }
        }
        printf("%d %d\n", kk, st[m].order);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 2637 장난감조립  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

ACM Craft


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



전의 게임 개발 (https://www.acmicpc.net/problem/1516)과 같은 문제다.


게임 개발은 모든 건물의 최소 건설 완료 시간을 물어봤다면, 이 문제는 한 건물만 물어본다.



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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int time[1001], in[1001];
int t, n, k, a, b, w;
 
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d %d"&n, &k);
        for (int i = 1; i <= n; ++i) {
            scanf("%d"&time[i]);
            in[i] = 0;
        }
 
        vector<vector<int>> vec(n + 1);
        for (int i = 0; i < k; ++i) {
            scanf("%d %d"&a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
 
        vector<int> ans(n + 1);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (!in[i]) {
                q.push(i);
                ans[i] = time[i];
            }
        }
 
        scanf("%d"&w);
        while (!q.empty()) {
            int m = 0;
            int cur = q.front();
            q.pop();
            if (cur == w)
                break;
 
            for (auto next : vec[cur]) {
                in[next]--;
 
                if (ans[next] < ans[cur] + time[next])
                    ans[next] = ans[cur] + time[next];
 
                if (!in[next])
                    q.push(next);
            }
        }
        printf("%d\n", ans[w]);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

게임 개발


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



테크트리를 타고 모든 건물을 지어야 한다. 모든 건물을 짓는데 시간이 얼마나 들까?


생각해야 할 점은 건물들이 동시에 지어질 수 있다는 점이다.


예를 들어 현재 배럭과 벙커를 지을 수 있다면, 배럭을 짓는데 시간이 더 오래 걸리므로 배럭 건설시간이 정답이 된다.



큐는 현재 지을 수 있는 건물(진입차수가 0이 된 노드)을 담고 있으므로,


큐를 건설시간이 작은 순으로 정렬되는 우선순위 큐로 바꾼다면, 맨 뒤에 있는 배럭이 정답에 반영될 것이다.



다르게 말하자면,


a->b (10)// c->b (20)라는 테크트리에 대해, 


b를 짓기 위해선 a와 c를 둘 다 지어야 하지만, b를 짓기 위한 준비 시간은 c만 포함된다.



따라서 b로 진입하는 두 간선 중 가벼운 a가 먼저 지어지면서 간선이 없어지지만, 무거운 c간선이 남아있으므로


정답에 반영되지 않는다.


다음으로 c간선이 없어지면서 b를 지을 수 있게되었다. 이제 가장 무거웠던 c간선의 20초가 정답에 들어간다.


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
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
struct build {
    int num, time;
};
bool operator <(const build& a, const build& b) {
    if (a.time != b.time)
        return a.time > b.time;
    return a.num > b.num;
}
build buildings[501];
 
int n, a, b, c;
int in[501];
 
int main() {
    scanf("%d"&n);
    vector<vector<int>> vec(n + 1);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d"&a);
        buildings[i].time = a;
 
        while (1) {
            scanf("%d"&a);
            if (a == -1)
                break;
 
            vec[a].push_back(i);
            in[i]++;
        }
    }
 
    priority_queue<build> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push({i,buildings[i].time});
    }
 
    while (!q.empty()) {
        int cur = q.top().num;
        q.pop();
 
        for (auto next : vec[cur]) {
            in[next]--;
            if (!in[next]) {
                buildings[next].time += buildings[cur].time;
                q.push({next, buildings[next].time});
            }    
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", buildings[i].time);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

음악프로그램





줄 세우기 문제(http://js1jj2sk3.tistory.com/94?category=755224)와 같은 위상정렬문제다.


다만 간선을 만드는 과정과 사이클의 유무를 확인하는 데 유의하자.


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
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int n, m, a, b, c;
int in[1001];
 
int main() {
    scanf("%d %d"&n, &m);
    vector<vector<int>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d"&a);
        scanf("%d"&b);
        for (int j = 1; j < a; ++j) {
            scanf("%d"&c);
            vec[b].push_back(c);
            in[c]++;
            b = c;
        }
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push(i);
    }
 
    vector<int> ans;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        ans.push_back(t);
 
        for (auto next : vec[t]) {
            in[next]--;
            if (!in[next])
                q.push(next);
        }
    }
 
    if (ans.size() != n) {
        printf("0");
        return 0;
    }
 
    for (auto a : ans)
        printf("%d\n", a);
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

문제집


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


위상정렬 문제.

다만 스페셜 저지가 아닌만큼, 같은 위상이라도 특수조건이 주어진다.

예제의 경우에, 3과 4는 같은 위상이지만, 조건3에 의해 3이 더 쉬운문제이므로 3을 먼저 풀어야 한다.

이제 3이 없어졌으니까(3이 뿜는 간선도 사라졌다) 문제 4와 1은 같은 위상이다. 조건 3에 의해 1을 먼저 푼다.


즉 큐는 큐지만, 문제 번호가 낮은 걸 먼저 pop해줄 자료구조로 우선순위 큐를 쓰면 풀 수 있다.

heap을 만들어서 풀어봤지만 속도는 같았다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
struct heap {
    int* arr;
    int cnt = 0;
 
    heap(int n) { arr = new int[n]; }
    ~heap() { delete[] arr; }
 
    void swap(int& a, int& b) {
        int t = a; a = b; b = t;
    }
 
    void push(int x) {
        ++cnt;
        arr[cnt] = x;
        int v = cnt;
 
        while (v / 2 >= 1 && arr[v/2> arr[v]) {
            swap(arr[v], arr[v / 2]);
            v /= 2;
        }
    }
 
    void pop() {
        arr[1= arr[cnt];
        cnt--;
 
        int v = 1;
        while (v * 2 <= cnt) {
            int iv = v * 2;
            if (iv + 1 <= cnt && arr[iv] > arr[iv + 1])
                iv++;
            if (arr[v] > arr[iv]) {
                swap(arr[v], arr[iv]);
                v = iv;
            }
            else
                break;
        }
    }
    int top() { return arr[1]; }
    bool empty() { return cnt == 0; }
};
 
int main() {
    scanf("%d %d"&n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d"&a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    //priority_queue<int> pq;
    heap pq(n + 1);
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            pq.push(i);
 
    while (!pq.empty()) {
        int t = pq.top();
        printf("%d ", t);
        pq.pop();
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                pq.push(next);
        }
    }
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

문제집


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


그래프가 유향 그래프라면, 노드 간에는 위상이 정해진다.


a노드에서 b노드로 진출하는 간선이 있다면, a와 b의 위상이 서로 다른 셈이다.



실생활에서 노드간의 위상은, 선수강과목이나 테크트리에서 찾아볼 수 있다.


넥서스가 있어야 게이트웨이를 지을수 있드시, 객체지향프로그래밍을 들어야 자료구조를 들을 수 있드시,


간선의 방향에 따라 노드간에 위상이 결정된다.



위상정렬은, 이와 같은 유향 그래프에서 노드 간의 위상을 순서대로 구하는 알고리즘이다.


따라서 유향그래프 내 사이클이 존재한다면, 즉 DAG이 아니라면 위상정렬할 수 없다.



여러가지 방법이 있지만, 주로 사용하는 진입차수를 이용한 풀이를 소개하고자 한다.


진입차수는 해당노드를 향한 간선의 개수를 뜻한다.


즉 1->3 // 2->3 의 간선이 있다면, 노드3의 진입차수는 2다.



위상정렬은 우선 모든 노드의 진입차수를 구하고 시작한다.


다음에는 진입차수가 0인 노드들을 전부 큐에 넣는다.


이제 큐에서 하나씩 꺼내면서 노드에서 나가는 간선들을 모두 제거한다.


현재 간선은 진입차수로 표현되었기 때문에, 진입차수를 표현하고 있는 데이터를 변경하면 되겠다.


제거하고 난 뒤 만약 진입차수가 0이 된 노드가 있다면 큐에 넣는다.



진입차수가 0인 노드들을 찾고, 딸린 간선을 제거하고,


다시 진입차수가 0인 노드들을 처리하는 부분문제로 이어진다고 생각하면 편하다.



사이클의 유무는 어떻게 판단할까?


만약 큐를 전부 소모했음에도 위상이 판단되지 않은 노드가 여전히 있다면 사이클때문임이 자명하다.



다음은 2252번 줄 세우기에 대한 해답이다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
int main() {
    scanf("%d %d"&n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d"&a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            q.push(i);
 
    while (!q.empty()) {
        int t = q.front();
        q.pop();
 
        printf("%d ", t);
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                q.push(next);
        }
    }
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

+ Recent posts