반응형

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

 

1833번: 고속철도 설계하기

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, 값이 음수이면 ans에 절댓값을 더해주고, 양수이면 arr 배열에 추가합니다.

 

2. arr 배열을 비용에 관하여 오름차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 비용을  ans에 더해주고, 이어진 노드들을 list에 저장합니다.

 

4. ans와 list.size()를 출력하고, 이어진 노드들을 차례대로 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N;
int ans;
vector<node> arr;
vector<pair<int, int>> list;
int vect[201];
 
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);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int cost;
            scanf("%d", &cost);
 
            if (i < j) {
                if (cost < 0) {
                    ans += -cost;
                    Union(i, j);
                }
                else if(cost>0) {
                    arr.push_back({ i,j,cost });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        const int u = next.u;
        const int v = next.v;
        const int w = next.w;
 
        if (Find(u) != Find(v)) {
            list.push_back({ u,v });
            Union(u, v);
            ans += w;
        }
    }
 
    printf("%d %d\n", ans, (int)list.size());
 
    for (int i = 0; i < list.size(); i++) {
        printf("%d %d\n", list[i].first, list[i].second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
반응형

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

 

18769번: 그리드 네트워크

재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 비용을  ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int vect[250001];
vector<node> arr;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int R, C;
        scanf("%d %d", &R, &C);
 
        arr.clear();
 
        for (int i = 1; i <= R * C; i++) {
            vect[i] = i;
        }
 
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C - 1; j++) {
                int num;
                scanf("%d", &num);
 
                arr.push_back({ (i - 1) * C + j, (i - 1) * C + j + 1,num });
            }
        }
 
        for (int i = 1; i <= R-1; i++) {
            for (int j = 1; j <= C; j++) {
                int num;
                scanf("%d", &num);
 
                arr.push_back({ (i - 1) * C + j, i * C + j,num });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        int ans = 0;
 
        for (auto& next : arr)
        {
            const int u = next.u;
            const int v = next.v;
            const int w = next.w;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                ans += w;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
반응형

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

 

9344번: 도로

어떤 나라에는 1부터 N까지 이름 붙여진 N개의 도시가 있다. 한 엔지니어는 모든 도시를 연결하는 도로를 건설하고자 한다. 즉, 모든 도시에 대해 항상 다른 어떤 도시로든 이동할 수 있어야 한다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, map 자료 구조에 이어진 노드들을 저장합니다.

 

3. p 노드와 q 노드가 연결되어 있다면 YES를 출력하고, 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
node arr[20000];
int vect[10001];
map<pair<int, int>, bool> visited;
 
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()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N, M, p, q;
        scanf("%d %d %d %d", &N, &M, &p, &q);
 
        //visited.clear();
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &arr[i].u, &arr[i].v, &arr[i].w);
        }
 
        sort(arr, arr + M, cmp);
 
        for (int i = 0; i < M; i++) {
            const int u = arr[i].u;
            const int v = arr[i].v;
            const int w = arr[i].w;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                visited[{u, v}] = true;
            }
        }
 
        if (visited[{p, q}] || visited[{q, p}]) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
반응형

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

 

1414번: 불우이웃돕기

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장하고, ans에 모든 랜선의 길이를 더해줍니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, ans에서 그 길이를 빼줍니다.

 

3. 연결된 간선의 길이가 N-1개라면 ans를 출력하고, 그렇지 않다면 -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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct node {
    int a, b, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N;
vector<node> arr;
int vect[51];
int ans;
 
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);
 
    for (int i = 1; i <= N; i++) {
        char temp[55];
        scanf("%s", temp);
        for (int j = 1; j <= N; j++) {
            if (temp[j - 1] >= 'a' && temp[j - 1] <= 'z') {
                arr.push_back({ i,j, temp[j - 1] - 'a' + 1 });
                ans += temp[j - 1] - 'a' + 1;
            }
            else if (temp[j - 1] >= 'A' && temp[j - 1] <= 'Z') {
                arr.push_back({ i,j,temp[j - 1] - 'A' + 27 });
                ans += temp[j - 1] - 'A' + 27;
            }
        }
 
        vect[i] = i;
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    int cnt = 0;
 
    for (auto& next : arr) {
        const int a = next.a;
        const int b = next.b;
        const int c = next.c;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans -= c;
            cnt++;
        }
    }
 
    if (cnt != N - 1) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
반응형

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

 

14950번: 정복자

서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고 arr 배열에 저장합니다.

 

2. 총 M번 for문을 돌면서 MST를 만들고, 간선을 이어줄 때마다 ans에 비용과 t를 더해줍니다.

 

3. ans를 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C < right.C;
}
 
int N, M, t;
node arr[30001];
int vect[10001];
 
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 %d %d", &N, &M, &t);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].C);
    }
 
    sort(arr, arr + M, cmp);
 
    long long ans = 0;
    int temp = 0;
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ans += C;
            ans += temp;
            temp += t;
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
반응형

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

 

27009번: Out of Hay

The cows have run out of hay, a horrible event that must be remedied immediately. Bessie intends to visit the other farms to survey their hay situation. There are N (2 ≤ N ≤ 2,000) farms (numbered 1..N); Bessie starts at Farm 1. She'll traverse some or

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고 arr 배열에 저장합니다.

 

2. 간선의 길이를 기준으로 오름차순으로 arr 배열을 정렬합니다.

 

3. Union-Find를 활용하여 모든 노드를 이어 주고, 그중 가장 긴 간선을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, L;
};
 
bool cmp(node left, node right)
{
    return left.L < right.L;
}
 
int N, M;
int vect[2001];
node arr[10000];
 
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 %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].L);
    }
 
    int ans = 0;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int L = arr[i].L;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ans = max(ans, L);
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
반응형

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

 

16202번: MST 게임

첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고 arr 배열에 저장합니다.

 

2. 총 K번 for문을 돌면서 MST를 만들고, 그중 가장 짧은 간선을 제거하면서 MST의 길이를 출력해 줍니다.

 

3. 만약 MST를 만들 수 없다면 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 #include<iostream>
 
using namespace std;
 
int N, M, K;
pair<int, int> arr[10001];
int vect[1001];
int Min = 1;
bool zero = false;
 
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 %d %d", &N, &M, &K);
 
    for (int i = 1; i <= M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int k = 0; k < K; k++) {
        int ans = 0;
        int temp = 987654321;
        if (zero) {
            printf("0 ");
            continue;
        }
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = Min; i <= M; i++) {
            const int a = arr[i].first;
            const int b = arr[i].second;
 
            if (Find(a) != Find(b)) {
                Union(a, b);
                ans += i;
                temp = min(temp, i);
            }
        }
 
        Min = temp + 1;
 
        for (int i = 2; i <= N; i++) {
            if (Find(1) != Find(i)) {
                printf("0 ");
                zero = true;
                break;
            }
        }
 
        if (zero != true) {
            printf("%d ", ans);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
반응형

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

 

21924번: 도시 건설

첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, ans에 더해줍니다.

 

2. 입력받은 간선을 길이를 기준으로 오름차순으로 정렬합니다.

 

3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어주고, ans에서 간선을 빼줍니다.

 

4. for문을 통해 2부터 N번 노드까지 탐색하면서 1번 노드와 부모 노드가 다른 노드가 하나라도 있다면 -1을 출력하고, 그렇지 않다면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int a;
    int b;
    ll c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, M;
ll ans;
int vect[100001];
node arr[500000];
 
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 %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %lld", &arr[i].a, &arr[i].b, &arr[i].c);
        ans += arr[i].c;
    }
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const ll c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans -= c;
        }
    }
 
    for (int i = 2; i <= N; i++) {
        if (Find(1) != Find(i)) {
            printf("-1");
            return 0;
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
반응형

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

 

13905번: 세부

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받습니다.

 

2. 입력받은 간선을 길이를 기준으로 내림차순으로 정렬합니다.

 

3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어줍니다.

 

4. s와 e 노드가 연결되면 연결된 간선 중 가장 짧은 간선의 길이를 출력합니다.

 

5. s와 e 노드가 연결될 수 없다면 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int h1;
    int h2;
    int k;
};
 
bool cmp(node left, node right)
{
    return left.k > right.k;
}
 
int N, M;
int s, e;
node arr[300001];
int vect[100001];
 
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 %d", &N, &M);
    scanf("%d %d", &s, &e);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].h1, &arr[i].h2, &arr[i].k);
    }
 
    int ans = 987654321;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int h1 = arr[i].h1;
        const int h2 = arr[i].h2;
        const int k = arr[i].k;
 
        if (Find(h1) != Find(h2)) {
            Union(h1, h2);
            ans = min(ans, k);
        }
 
        if (Find(s) == Find(e)) {
            printf("%d", ans);
            return 0;
        }
    }
 
    printf("0");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
반응형

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

 

6497번: 전력난

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받는 모든 길의 거리를 ans에 더해줍니다.

 

2. Union-Find를 이용하여 노드들을 이어지고, 이어 줄 때마다 ans에서 이어진 길의 거리를 빼줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int x;
    int y;
    int z;
};
 
bool cmp(node left, node right)
{
    return left.z < right.z;
}
 
int m, n;
int vect[200000];
 
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()
{
    while (1) {
        scanf("%d %d", &m, &n);
        if (m == 0 && n == 0) break;
 
        int ans = 0;
        vector<node> arr;
 
        for (int i = 0; i < m; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < n; i++) {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            arr.push_back({ x,y,z });
            ans += z;
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int x = next.x;
            const int y = next.y;
            const int z = next.z;
 
            if (Find(x) != Find(y)) {
                Union(x, y);
                ans -= z;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23
[ 백준 ] 18223번 - 민준이와 마산 그리고 건우 (C++)  (0) 2023.02.21
[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19

+ Recent posts

티스토리툴바