반응형

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<string, int> m;
string str[1000];
int cnt[1000];
map<string, vector<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
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
[ 백준 ] 3780번 - 네트워크 연결 (C++)  (0) 2023.10.09
[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08

+ Recent posts

티스토리툴바