반응형

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

 

17490번: 일감호에 다리 놓기

2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드에서 돌을 놓아야 하는 개수를 입력받아 cost 배열에 저장합니다.

 

2. 끊긴 간선들은 isEdge 배열에 true로 저장합니다.

 

3. 끊긴 간선들을 제외하고 Union-Find를 이용하여 이어줍니다.

 

4. 이어줄 때 이어진 노드들 중 돌을 놓아야 하는 개수가 가장 적은 값으로 cost 배열을 갱신해줍니다.

 

5. 섬의 노드 번호를 0으로 두고, 모든 노드들을 0과 이어주면서 cost가 K를 넘으면 NO를 출력하고, 넘지 않으면 YES를 출력합니다.

 

6. 꼬리를 물고 이어져 있으므로 M의 값이 1보다 작거나 같으면 무조건 YES를 출력해줍니다.

 

[ 소스코드 ]

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<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
ll K;
int cost[1000001];
bool isEdge[1000001];
int vect[1000001];
 
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);
 
    cost[pa] = cost[pb] = min(cost[pa], cost[pb]);
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d %lld", &N, &M, &K);
 
    if (M <= 1) {
        printf("YES");
        return 0;
    }
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        scanf("%d", &cost[i]);
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a != N || b != 1) {
            if (a > b) {
                swap(a, b);
            }
        }
 
        isEdge[a] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!isEdge[i]) {
            if (i == N) {
                Union(1, N);
            }
            else {
                Union(i + 1, i);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (Find(i) != 0) {
            K -= cost[Find(i)];
            Union(0, i);
        }
 
        if (K < 0) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27

+ Recent posts

티스토리툴바