반응형

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

 

22116번: 창영이와 퇴근

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, arr 배열에 저장합니다.

 

2. visited 배열을 만들어 해당 구간에 도착했을 때 경사로 차가 가장 적었을 때의 값을 저장합니다.

 

3. ans에 경사로 차 중 가장 큰 값을 저장합니다.

 

4. 다익스트라를 이용하여 경사로의 높이차가 작은 구간부터 방문하고, N - 1, N - 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<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int y, x, h;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.h < right.h;
    }
};
 
int N;
int arr[1000][1000];
int visited[1000][1000];
int ans;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = 1111111111;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int h = pq.top().h;
        pq.pop();
 
        if (visited[y][x] < h) continue;
 
        ans = max(ans, h);
 
        if (y == N - 1 && x == N - 1) {
            cout << ans;
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
                if (visited[yy][xx] > diff) {
                    visited[yy][xx] = diff;
                    pq.push({ yy,xx,diff });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
반응형

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

 

4343번: Arctic Network

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt를 선언합니다.

 

2. vect[ i ] = i로 초기화하고, 각 지점까지의 거리를  arr 배열에 저장합니다.

 

3. arr 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 각 지점들을 연결하고, 연결될 때마다 cnt++를 해주고, cnt == P - S일 때 거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int u, v;
    double d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int T, S, P;
vector<node> arr;
pair<int, int> pos[501];
int vect[501];
int cnt;
 
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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    cout << fixed;
    cout.precision(2);
 
    for (int t = 0; t < T; t++) {
        cin >> S >> P;
 
        arr.clear();
        cnt = 0;
 
        for (int i = 1; i <= P; i++) {
            int x, y;
            cin >> x >> y;
            pos[i] = { x,y };
            vect[i] = i;
        }
 
        for (int i = 1; i <= P - 1; i++) {
            for (int j = i + 1; j <= P; j++) {
                int x = pos[i].first - pos[j].first;
                int y = pos[i].second - pos[j].second;
                double d = sqrt(x * x + y * y);
                arr.push_back({ i,j,d });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int u = next.u;
            const int v = next.v;
            const double d = next.d;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                cnt++;
            }
 
            if (cnt == P - S) {
                cout << d << '\n';
                break;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
반응형

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

 

15789번: CTP 왕국은 한솔 왕국을 이길 수 있을까?

입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다. 입력의 마지막 줄에 CT

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 왕국을 이어주고, 이을 때마다 power 배열에 값을 경신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 CTP 왕국이나 한솔 왕국에 속하지 않은 왕국들의 동맹국들의 수를 ans 배열에 저장합니다.

 

5. ans 배열을 내림차순으로 정렬하고, K개까지 동맹국을 더해줍니다.

 

6. 그 결과를 출력합니다.

 

[ 소스코드 ]

 

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<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
int vect[100001];
int power[100001];
int visited[100001];
vector<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;
    power[pa] += power[pb];
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        power[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int X, Y;
        scanf("%d %d", &X, &Y);
 
        if (Find(X) != Find(Y)) {
            Union(X, Y);
        }
    }
 
    int C, H, K;
    scanf("%d %d %d", &C, &H, &K);
    int cnt = 0;
 
    if (K) {
        for (int i = 1; i <= N; i++) {
            int temp = Find(i);
            if ((Find(C) != temp) && (temp != Find(H))) {
                if (visited[temp] == 0) {
                    visited[temp] = 1;
                    ans.push_back({ power[temp] });
                }
            }
        }
    }
 
    sort(ans.begin(), ans.end(), greater<>());
 
    int temp = power[Find(C)];
 
    for (int i = 0; i < min((int)ans.size(), K); i++) {
        temp += ans[i];
    }
    printf("%d", temp);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
반응형

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

 

14595번: 동방 프로젝트 (Large)

첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. x와 y의 부모노드가 다르다면 y부터 x까지 for문을 통해 돌면서 x와 y사이에 있는 모든 동방들을 x와 이어줍니다. 이때, j = Find( j ) 를 통해 j를 갱신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. 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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[1000001];
int visited[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);
 
    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++) {
        int x, y;
 
        scanf("%d %d", &x, &y);
 
        if (Find(x) != Find(y)) {
            for (int j = y; j > x; j--) {
                j = Find(j);
                Union(x, j);
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
반응형

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

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 뉴런을 이어주고, 이미 이어져 있다면 ans++를 해줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. 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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[100001];
int ans;
int visited[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);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
        else {
            ans++;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans - 1);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
반응형

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

 

25545번: MMST

첫째 줄에 그래프의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 200\,000$, $N-1 \leq M \leq 500\,000)$ 둘째 줄부터 $M$줄에 걸쳐 $i$번째 간선의 정보가 $(U_i, V_i, C_i)$와 같이 주어진다. 이는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N > M 인 경우에는 스패닝 트리가 최대 하나밖에 나오지 않기 때문에 해당 경우에는 MMST가 나올 수 없습니다.

 

2. N <= M 인 경우에는 모든 간선의 길이가 다르기 때문에 스패닝 트리가 최소 3개가 있고  그렇기 때문에 MMST가 최소 1개 있습니다.

 

3. MST를 만들고 거기에 포함되지 않은 간선이 포함된 스패닝 트리는 무조건 MMST 가 되므로 이를 활용하여 MMST를 구합니다.

 

[ 소스코드 ]

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
100
101
102
103
104
105
106
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct edge {
    int num;
    int from;
    int to;
    int dist;
};
 
bool Greater(edge left, edge right)
{
    return left.dist < right.dist;
}
 
bool Less(edge left, edge right)
{
    return left.dist > right.dist;
}
 
int N, M;
edge Edge[500000];
vector<int> ans;
int visited[500000];
int vect[200001];
 
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);
 
    if (N > M) {
        printf("NO");
        return 0;
    }
 
    for (int i = 0; i < M; i++) {
        int U, V, C;
        scanf("%d %d %d", &U, &V, &C);
        Edge[i] = { i + 1,U,V,C };
    }
 
    sort(Edge, Edge + M, Greater);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            visited[num] = 1;
        }
    }
    
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    int flag = false;
 
    for (int i = 0; i < M; i++) {
        const int num = Edge[i].num;
        if (visited[num] == 0) {
            ans.push_back(num);
            Union(Edge[i].from, Edge[i].to);
            break;
        }
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans.push_back(num);
        }
    }
 
    printf("YES\n");
    for (int num : ans) {
        printf("%d ", num);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
반응형

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
반응형

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

 

10723번: 판게아 1

첫 줄에는 테스트 케이스의 수 \(T\)가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 \(n\)과 도로가 건설된 횟수 \(m\)이 공백으로 구분되어 주어진다. 다음 \(n - 1\)줄에 태초

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. arr 배열을 오름차순으로 정렬합니다.

 

3. 새로운 간선을 입력받을 때마다 mst를 새로 만들어 줍니다.

 

4. 3의 과정에서 새로운 간선이 이전의 mst의 가장 긴 간선보다 길다면 mst를 다시 만들어 줄 필요가 없으므로 넘어갑니다.

 

5. 만들어지는 모든 mst를 XOR 해 ans에 저장합니다.

 

6. 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
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int u, v, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int vect[100000];
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 n, m;
        scanf("%d %d", &n, &m);
 
        arr.clear();
 
        for (int i = 1; i < n; i++) {
            int u, c;
            scanf("%d %d", &u, &c);
            arr.push_back({ i,u,c });
        }
 
        int Max = 987654321;
        ll temp = 0;
        ll ans = 0;
 
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
 
            arr.push_back({ u,v,c });
 
            if (Max > c) {
                temp = 0;
                Max = 0;
 
                for (int j = 0; j < n; j++) {
                    vect[j] = j;
                }
 
                sort(arr.begin(), arr.end(), cmp);
 
                for (auto& next : arr) {
                    const int u = next.u;
                    const int v = next.v;
                    const int c = next.c;
 
                    if (Find(u) != Find(v)) {
                        Union(u, v);
                        temp += c;
                        Max = max(Max, c);
                    }
                }
            }
            
            if (i == 0) {
                ans = temp;
            }
            else {
                ans ^= temp;
            }
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
반응형

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

 

 

[ 문제풀이 ]

 

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

 

2. arr 배열을 내림차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 간선의 비용을  ans에 더해주고, 개수를 cnt에 저장합니다.

 

4. cnt가 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
#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;
node arr[20000];
int vect[1001];
 
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].C);
    }
 
    sort(arr, arr + M, cmp);
 
    int ans = 0;
    int cnt = 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;
            cnt++;
        }
    }
 
    if (cnt != N - 1) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
반응형

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

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

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
#include<iostream>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N, M;
int ans;
int vect[1001];
pair<int, int> 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()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &N, &M);
        ans = 0;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &arr[i].first, &arr[i].second);
        }
 
        for (int i = 0; i < M; i++) {
            const int a = arr[i].first;
            const int b = arr[i].second;
 
            if (Find(a) != Find(b)) {
                Union(a, b);
                ans++;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15

+ Recent posts

티스토리툴바