반응형

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

 

21276번: 계보 복원가 호석

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 조상으로부터 자손으로 이어지는 단방향 그래프를 list 배열에 저장합니다.

 

2. 1과 동시에 조상의 개수를 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.

 

3. queue를 돌면서 cnt[ i ]가 0일 때 queue에 해당 자손을 넣어주고, 그때의 조상이 직계 조상이므로 child 배열에 해당 자손을 넣어줍니다.

 

4. 가장 초기에 cnt[ i ]가 0인 조상은 가문의 시조이므로 parent 배열에 넣어줍니다.

 

5. 조건에 맞게 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
 
using namespace std;
 
int N, M;
map<stringint> m;
string str[1000];
int cnt[1000];
map<stringvector<string>> child;
vector<int> list[1000];
vector<string> parent;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> str[i];
        m[str[i]] = i;
    }
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        string tmp[2];
        cin >> tmp[0>> tmp[1];
        cnt[m[tmp[0]]]++;
        list[m[tmp[1]]].push_back(m[tmp[0]]);
    }
 
    queue<int> q;
 
    for (int i = 0; i < N; i++) {
        if (cnt[i] == 0) {
            q.push(i);
            parent.push_back(str[i]);
        }
    }
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            cnt[next]--;
            if (cnt[next] == 0) {
                child[str[cur]].push_back(str[next]);
                q.push(next);
            }
        }
    }
 
    sort(parent.begin(), parent.end());
 
    cout << parent.size() << '\n';
 
    for (auto& next : parent) {
        cout << next << ' ';
    }
 
    cout << '\n';
 
    sort(str, str + N);
 
    for (int i = 0; i < N; i++) {
        cout << str[i] << ' ' << child[str[i]].size() << ' ';
        sort(child[str[i]].begin(), child[str[i]].end());
        for (auto& next : child[str[i]]) {
            cout << next << ' ';
        }
        cout << '\n';
    }
}
cs
반응형
반응형

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

 

14567번: 선수과목 (Prerequisite)

3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 선수 과목과 후수 과목으로 이어지는 단방향 그래프를 만들어줍니다.

 

2. 1과 동시에 선수과목이 몇 개 필요한지 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.

 

3. queue를 돌면서 cnt[ i ]가 0이면 계속 queue에 넣어주면서 선수과목이 몇 개 필요한지 ans에 저장합니다.

 

4. 1부터 N까지 ans[ i ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
int cnt[1001];
int ans[1001];
vector<int> list[1001];
 
int main()
{
    scanf("%d %d"&N, &M);
    queue<int> q;
 
    for (int i = 0; i < M; i++) {
        int A, B;
        scanf("%d %d"&A, &B);
 
        list[A].push_back(B);
        cnt[B]++;
    }
 
    for (int i = 1; i <= N; i++) {
        if (cnt[i] == 0) {
            q.push(i);
            ans[i] = 1;
        }
    }
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            cnt[next]--;
            if (cnt[next] == 0) {
                q.push(next);
                ans[next] += ans[cur] + 1;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
반응형

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

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 작업이 끝나는 시간을 저장할 cost 배열을 만듭니다.

 

2. 선행 작업이 모두 자신보다 숫자가 작은 작업이므로 앞에서 진행된 작업 중 가장 늦게 끝난 작업에 해당 작업이 끝나는데 걸리는 시간을 더해 cost에 저장해줍니다.

 

3. cost 배열에서 가장 큰 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int cost[10001];
int ans;
 
int main()
{
    scanf("%d"&N);
 
    for (int i = 1; i <= N; i++) {
        int c, n;
        scanf("%d %d"&c, &n);
        if (n == 0) cost[i] = c;
        for (int j = 0; j < n; j++) {
            int task;
            scanf("%d"&task);
            cost[i] = max(cost[i], cost[task] + c);
        }
        ans = max(ans, cost[i]);
    }
 
    printf("%d", ans);
}
cs
반응형
반응형

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

 

2637번: 장난감 조립

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 완제품에서부터 부품 쪽으로 내려가면서 개수를 저장해야 하므로, X -> Y 방향으로 단방향 그래프를 만들어줍니다.

 

2. 1과 동시에 중간 부품이 몇 번 필요한지 in [ Y ]++를 통해 저장해 주고, basic [ X ] = 1을 통해 기초 부품인지 아닌지 체크해 줍니다.

 

3. 위상정렬을 통해 N번부터 ans 배열에 필요한 부품의 개수를 저장합니다.

 

4. 하위 부품의 개수는 ans [next] += ans [cur] * next.cnt로 저장합니다.

 

5. basic [ i ] != 1인 부품에 대해서 ans [ i ]를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
vector<pair<intint>> list[101];
int ans[101];
int basic[101];
int in[101];
 
int main()
{
    scanf("%d %d"&N, &M);
 
    for (int i = 0; i < M; i++) {
        int X, Y, K;
        scanf("%d %d %d"&X, &Y, &K);
        list[X].push_back({ Y,K });
        basic[X] = 1;
        in[Y]++;
    }
 
    queue<int> q;
    q.push(N);
    ans[N] = 1;
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            ans[next.first] += ans[cur] * next.second;
            in[next.first]--;
            if (in[next.first] == 0) {
                q.push(next.first);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (basic[i] != 1) {
            printf("%d %d\n", i, ans[i]);
        }
    }
}
cs
반응형
반응형

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

 

1948번: 임계경로

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를.

rudalsd.tistory.com

 

먼저 최장 거리를 얻는 방법은 다음과 같습니다.

 

1. queue에 시작 노드를 넣고 bfs를 시작합니다.

 

2. 위상 정렬 알고리즘을 이용하여 해당 노드까지 오는 모든 길의 걸리는 시간 중 가장 오래 걸리는 시간을 dist 배열에 저장해줍니다.

 

3. 현재 노드까지 오는 모든 길을 탐색하였으면 queue에 넣어줍니다.

 

4. 마지막 노드에 도착했을 때 거리를 return 해주면 최장 거리를 얻을 수 있습니다.

 

이 최장 거리를 이용하여 오는데 지나온 도로를 찾을 수 있습니다.

 

마찬가지로 bfs를 통해 (현재 노드까지 오는데 걸리는 거리 - 다음 노드까지의 거리 == 다음 노드까지의 최장 거리) 일 때 그 도로는 최장 거리로 가는 도로에 포함되므로 ret에 1을 더해줍니다.

 

방문했던 노드에는 다시 방문하면 안 되므로 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
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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n, m;
int from, to;
vector<node> list[10001];
vector<node> r_list[10001];
int cnt[10001], dist[10001];
int visited[10001];
 
 
int Longest_dist(int from)        //가장 오래걸리는 시간 구하기
{
    queue<node> q;
    q.push({ from, 0 });
 
    while (!q.empty())
    {
        int cur = q.front().to;
        int cDist = q.front().dist;
        q.pop();
 
        if (cur == to) {
            return cDist;
        }
 
        for (int i = 0; i < list[cur].size(); i++) {
            int next = list[cur][i].to;
            int nDist = list[cur][i].dist;
 
            cnt[next]--;
            dist[next] = max(dist[next], cDist + nDist);    //다음 노드까지 갈 수 있는 최대 거리
 
            if (cnt[next] == 0) {    //다음 노드까지 갈 수 있는 모든 방법으로 갔을 때
                q.push({ next,dist[next] });
            }
        }
    }
}
 
int Find_road(int max)                //최대 거리로 갈 수 있는 도로 찾기
{
    int ret = 0;
 
    queue<node> q;
    q.push({ to, max });
 
    while (!q.empty())
    {
        int cur = q.front().to;
        int cDist = q.front().dist;
        q.pop();
 
        if (visited[cur] == 1continue;
        visited[cur] = 1;
 
        for (int i = 0; i < r_list[cur].size(); i++) {
            int next = r_list[cur][i].to;
            int nDist = r_list[cur][i].dist;
 
            if (cDist - nDist == dist[next]) {
                ret++;
                if (visited[next] != 1) {
                    q.push({ next,cDist - nDist });
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d"&a, &b, &c);
        list[a].push_back({ b,c });
        r_list[b].push_back({ a,c });
        cnt[b]++;
    }
 
    cin >> from >> to;
 
    int max = Longest_dist(from);
    int cnt = Find_road(max);
 
    cout << max << endl << cnt;
}
cs
반응형
반응형

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란?

 

위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방문해야 현재 노드에 방문할 수 있습니다. 위상 정렬 알고리즘선행 노드무조건 수행되어야 하기 때문에 사이클이 발생하지 않습니다.

 

 

2. 위상 정렬 알고리즘(Topological Sort Algorithm) 동작 원리?

 

위상 정렬이란 선행 노드가 수행이 되었을 때, 즉 진입 차수가 0일 때 현재 노드를 방문할 수 있습니다.

 

 

위 그래프의 진입 차수는 다음과 같습니다.

 

 

이때 진입 차수가 0인 노드들을 queue에 넣어줍니다.

 

queue

 

queue에서 숫자를 하나씩 빼주면서 연결되어 있는 노드의 진입 차수를 하나씩 빼주면서 진입 차수가 0이 되면 queue에 넣어줍니다.

 

queue
위상 순서

위와 같은 방법으로 반복해줍니다.

queue
위상 순서

 

queue
위상 순서

 

queue
위상 순서

 

queue
위상 순서

 

위상 순서

 

위상 정렬을 이용하여 다음 문제들을 풀 수 있습니다.

https://rudalsd.tistory.com/73?category=1064612 

 

[ 백준 ] 1948번 - 임계경로 (C++)

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음..

rudalsd.tistory.com

 

 

 

 

 

 

반응형

+ Recent posts