반응형

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

 

6091번: 핑크 플로이드

재현이는 N개의 정점으로 이루어진 트리를 가지고 있었다. 트리는 1~N까지의 번호가 정점에 매겨져 있었으며, 트리를 잇는 N-1개의 간선에는 두 정점을 잇는 거리가 저장되어 있었다. 재현이는 트

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드들 사이의 거리를 입력받으면서 pq에 거리순으로 push 합니다.

 

2. Union Find를 활용하여 시작 노드와 도착 노드의 부모가 다르다면 Union 하면서 인접 리스트에 추가합니다.

 

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
 
using namespace std;
 
int N;
int vect[1050];    //부모
vector<int> list[1050];    //인접 리스트
 
struct node {
    int from;
    int to;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int Find(int num)        //부모 찾기
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)    //합치기
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d", &N);
 
    priority_queue<node, vector<node>, cmp> pq;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 1; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int dist;
            scanf("%d", &dist);
            pq.push({ i,j,dist });    //거리순으로 push
        }
    }
 
    while (!pq.empty()) {
        const int from = pq.top().from;
        const int to = pq.top().to;
        const int dist = pq.top().dist;
        pq.pop();
 
        if (Find(from) != Find(to)) {    //부모가 다르다면
            Union(from, to);            //합치고
            list[from].push_back(to);    //인접 리스트 추가
            list[to].push_back(from);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        sort(list[i].begin(), list[i].end());    //정렬
        printf("%d ", list[i].size());
        for (auto next : list[i]) {
            printf("%d ", next);
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07
[ 백준 ] 5427번 - 불 (C++)  (0) 2022.12.05
[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03

+ Recent posts

티스토리툴바