반응형

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

 

2406번: 안정적인 네트워크

첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들어서 arr 배열에 u, v, c를 각각 저장합니다.

 

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

 

3. 1번 노드를 제외한 나머지 노드들을 mst로 이어주어야 하므로 arr 배열을 만들 때 1번 노드를 제외하고 넣어줍니다.

 

4. Union-Find를 이용하여 노드들을 연결시켜 주고, 이때 cost에 c를 더해주고, ans 배열에 각각의 노드를 push 해줍니다.

 

5. cost와 ans.size()를 출력하고, 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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int n, m;
int vect[1001];
vector<node> arr;
vector<pair<int, 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 %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);
        Union(x, y);
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int cost;
            scanf("%d", &cost);
            if (i < j && i != 1) {
                arr.push_back({ i,j,cost });
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    int cost = 0;
 
    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);
            cost += c;
            ans.push_back({ u, v });
        }
    }
 
    printf("%d %d\n", cost, (int)ans.size());
 
    for (auto& next : ans) {
        printf("%d %d\n", next.first, next.second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18223번 - 민준이와 마산 그리고 건우 (C++)  (0) 2023.02.21
[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
반응형

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

 

20010번: 악덕 영주 혜유

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들어서 arr 배열에 a, b, c를 각각 저장합니다.

 

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

 

3. Union-Find를 이용하여 마을들을 연결하고, 열결이 될 때마다 ans에 c를 더해줍니다.

 

4. 또한, 연결이 될 때마다 연결이 된 교역로만으로 그래프를 다시 만듭니다.

 

5. 새로 만든 그래프를 이용하여 한 마을에서 가장 먼 마을을 구하고, 다시 그 마을로부터 가장 먼 마을까지의 거리를 따로 저장합니다.

 

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>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, K;
node arr[1000000];
int vect[1000];
vector<pair<int,int>> list[1000];
int visited[1000];
int Max;
int start;
 
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;
}
 
void dfs(int n, int cost)
{
    if (cost > Max) {
        Max = cost;
        start = n;
    }
 
    for (auto& next : list[n]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, cost + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c);
    }
 
    sort(arr, arr + K, cmp);
 
    int ans = 0;
 
    for (int i = 0; i < K; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const int c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            list[a].push_back({ b,c });
            list[b].push_back({ a,c });
            Union(a, b);
            ans += c;
        }
    }
 
    visited[0] = 1;
    dfs(0, 0);
 
    Max = 0;
    fill(visited, visited + N, 0);
 
    visited[start] = 1;
    dfs(start, 0);
 
    printf("%d\n%d", ans, Max);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
반응형

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

 

1944번: 복제 로봇

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 미로를 입력받고, S와 K의 좌표에 번호를 붙입니다.

 

2. 2중 for문을 이용하여 S와 K의 모든 좌표들끼리 연결하고, edge 배열에 시작점과 도착점, 거리를 저장합니다.

 

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

 

4. Union-Find를 이용하여 모든 노드를 연결하고, ans에 거리를 더합니다.

 

5. 위의 과정에서 노드를 연결할 때마다 cnt++ 해줍니다.

 

6. cnt == M일 경우 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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char arr[51][51];
int check[251][251];
int key[51][51];
vector<node> edge;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int vect[251];
 
void getEdge(int y, int x)
{
    int u = key[y][x];
    int visited[50][50] = { 0 };
    queue<node> q;
    q.push({ y,x,0 });
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().u;
        const int x = q.front().v;
        const int cnt = q.front().d;
        q.pop();
 
        if ((arr[y][x] == 'S' || arr[y][x] == 'K') && cnt != 0) {
            int v = key[y][x];
            if (check[u][v] != 1 && check[v][u] != 1) {
                edge.push_back({ u,v,cnt });
                check[u][v] = 1;
                check[v][u] = 1;
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy > 0 && yy < N - 1 && xx>0 && xx < N - 1) {
                if (arr[yy][xx] != '1' && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}
 
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 = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 1; i <= M; i++) {
        vect[i] = i;
    }
 
    int cnt = 1;
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S') {
                key[i][j] = 0;
            }
            else if(arr[i][j] == 'K'){
                key[i][j] = cnt++;
            }
        }
    }
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S' || arr[i][j] == 'K') {
                getEdge(i, j);
            }
        }
    }
 
    sort(edge.begin(), edge.end(), cmp);
 
    int ans = 0;
    cnt = 0;
 
    for (auto& next : edge) {
        const int u = next.u;
        const int v = next.v;
        const int d = next.d;
 
        if (Find(u) != Find(v)) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == M) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
반응형

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

 

14621번: 나만 안되는 연애

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 여초와 남초를 저장할 univ 배열을 만들고, 각자의 부모를 저장할 vect 배열을 만듭니다.

 

2. 간선을 입력받고, 비용을 기준으로 오름차순으로 정렬합니다.

 

3. Union-Find를 이용하여 각각의 노드가 부모가 서로 다르고, 대학도 서로 다르다면 합쳐줍니다.

 

4. 이 때, ans에 비용을 더해주고, cnt++를 해줍니다.

 

5. 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
69
70
71
72
73
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char univ[1001];
int vect[1001];
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++) {
        getchar();
        scanf("%c", &univ[i]);
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].u, &arr[i].v, &arr[i].d);
    }
 
    sort(arr, arr + M, cmp);
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        const int u = arr[i].u;
        const int v = arr[i].v;
        const int d = arr[i].d;
 
        if (Find(u) != Find(v) && univ[u] != univ[v]) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == N - 1) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
반응형

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

 

1368번: 물대기

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어

www.acmicpc.net

 

 

[ 문제풀이 ]

1. vect 배열을 만들고 vect [ i ] = i로 초기화해 줍니다.

 

2. node struct를 만들어 i, j, cost를 저장할 수 있는 vect <node> arr를 만듭니다.

 

3. 우물 팔 때 드는 비용을 입력받고, arr에 i, 0, W를 저장합니다.

 

4. i, j, Pi,j를 입력받고, arr에 저장합니다.

 

5. arr 배열을 cost를 기준으로 오름차순으로 정렬합니다.

 

6. for문을 돌며 Union-Find를 이용하여 각 노드들을 이어주고, ans에 비용을 저장해 줍니다.

 

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

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

[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02
[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
반응형

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

 

10423번: 전기가 부족해

첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째

www.acmicpc.net

 

 

[ 문제풀이 ]

1. vect 배열을 만들고 vect [ i ] = i로 초기화해 줍니다.

 

2. 발전소가 설치된 노드를 입력받고, vect [ plant ] = 0으로 초기화합니다.

 

3. node struct를 만들고, node arr [ 100001 ] 배열을 만들어 각각의 u, v, w를 저장합니다.

 

4. arr 배열을 w를 기준으로 오름차순으로 정렬합니다.

 

5. for문을 돌며 Union-Find를 이용하여 각 노드들을 이어주고, 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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int w;
};
 
struct cmp {
    bool operator()(node left, node right) {
        return left.w < right.w;
    }
};
 
int N, M, K;
int vect[1001];
node arr[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 %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < K; i++) {
        int plant;
        scanf("%d", &plant);
        vect[plant] = 0;
    }
 
    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());
 
    int ans = 0;
 
    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);
            ans += w;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
반응형

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

 

13418번: 학교 탐방하기

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들고, node arr [ 500000 ] 배열을 만들어 각각의 A, B, C를 저장합니다. 이때, 오르막길이 0이므로 0이 입력되면 C = 1, 1이 입력되면 C = 0으로 저장합니다.

 

2. arr를 오름차순으로 정렬하고, vect 배열을 초기화한 후 Union-Find를 이용하여 각 노드들을 이어주고, cost를 max에 더해줍니다.

 

3. arr를 내림차순으로 정렬하고, vect 배열을 초기화한 후 Union-Find를 이용하여 각 노드들을 이어주고, cost를 min에 더해줍니다.

 

4. max * max - min * min을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int A;
    int B;
    int cost;
};
 
struct Greater {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
struct Less {
    bool operator()(node right, node left) {
        return left.cost > right.cost;
    }
};
 
int N, M;
int vect[1001];
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;
}
 
ll fatigue(ll a)
{
    ll ret = a;
 
    for (int i = 1; i <= M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int cost = arr[i].cost;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ret += cost;
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i <= M; i++) {
        scanf("%d %d", &arr[i].A, &arr[i].B);
        int cost;
        scanf("%d", &cost);
        if (cost == 0) {
            arr[i].cost = 1;
        }
        else {
            arr[i].cost = 0;
        }
    }
 
    ll max, min;
 
    for (int i = 0; i <= N; i++) {
        vect[i] = i;
    }
 
    vect[1] = 0;
 
    sort(arr + 1, arr + M + 1, Greater());
 
    max = fatigue(arr[0].cost);
 
    for (int i = 0; i <= N; i++) {
        vect[i] = i;
    }
 
    vect[1] = 0;
 
    sort(arr + 1, arr + M + 1, Less());
 
    min = fatigue(arr[0].cost);
 
    printf("%lld", max * max - min * min);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
반응형

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

 

16398번: 행성 연결

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr[ 1001 ][ 1001 ]배열에 값을 입력 받고, i < j일 때 값을 priority_queue에 넣습니다.

 

2. Union-Find를 이용하여 부모가 같지 않다면 두 노드를 합치고, ans에 cost를 더해줍니다.

 

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<queue>
#define ll long long
 
using namespace std;
 
int N;
int vect[1001];
ll arr[1001][1001];
 
struct node {
    int from;
    int to;
    ll cost;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
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 = 1; j <= N; j++) {
            scanf("%lld", &arr[i][j]);
            if (i < j) {
                pq.push({ i,j,arr[i][j] });
            }
        }
    }
 
    ll ans = 0;
 
    while (!pq.empty()) {
        const int a = pq.top().from;
        const int b = pq.top().to;
        const int cost = pq.top().cost;
        pq.pop();
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans += cost;
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
반응형

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

 

1922번: 네트워크 연결

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. pq에 출발점, 도착점과 거리를 넣습니다.

 

2. pq에서 하나씩 뽑아서 크루스칼 알고리즘을 통해  MST를 찾고, ans에 dist를 더해줍니다.

 

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<queue>
 
using namespace std;
 
int N, M;
int vect[1001];
 
struct node {
    int a;
    int b;
    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 %d", &N, &M);
    priority_queue<node, vector<node>, cmp> pq;
 
    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", &a, &b, &c);
        pq.push({ a,b,c });
    }
 
    int ans = 0;
 
    while (!pq.empty()) {
        const int a = pq.top().a;
        const int b = pq.top().b;
        const int dist = pq.top().dist;
        pq.pop();
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans += dist;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
[ 백준 ] 19538번 - 루머 (C++)  (0) 2022.12.24
[ 백준 ] 14395번 - 4연산 (C++)  (0) 2022.12.22
[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
반응형

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

 

16393번: Lost Map

The first line of input will contain the integer n (2 ≤ n ≤ 2 500), the number of villages in this region. The next n lines will contain n integers each. The jth integer of the ith line is the distance from village i to village j. All distances are gre

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 도시마다 거리를 입력받고 i < j 일 때만 vector에 거리, 시작 도시, 도착 도시를 push 해 줍니다.

 

2. vector를 거리가 짧은 순으로 정렬해줍니다.

 

3. for문을 통해 vector를 돌며 Union Find를 이용하여 i와 j의 부모가 다를 때 i와 j를 합쳐주며 ans에 i, j를 넣어줍니다.

 

4. 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
#include<iostream>
#include<algorithm>
#include<vector>
#include<tuple>
#define ti tuple<int,int,int>
 
using namespace std;
 
int N;
int vect[2501];
vector<pair<int,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++) {
        vect[i] = i;
    }
 
    vector<ti> pq;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int dist;
            scanf("%d", &dist);
            if (i < j) {
                pq.emplace_back(dist, i, j);
            }
        }
    }
 
    sort(pq.begin(), pq.end());
 
    for (auto& next : pq) {
        int a = get<1>(next);
        int b = get<2>(next);
        if (Find(a) != Find(b)) {
            Union(a,b);
            ans.emplace_back(a, b);
        }
    }
 
    for (auto next : ans) {
            printf("%d %d\n", next.first, next.second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07
[ 백준 ] 6091번 - 핑크 플로이드 (C++)  (0) 2022.12.06
[ 백준 ] 5427번 - 불 (C++)  (0) 2022.12.05

+ Recent posts

티스토리툴바