반응형

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

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

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

 

1774번: 우주신과의 교감

(1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 좌표를 입력받고 모든 좌표 간의 거리를 pq에 넣습니다. 이때, 점 사이 거리를 제곱한 값이 int를 벗어나므로 long long형으로 제곱해줍니다.

 

2. Union Find를 통해 입력 받은 신들끼리 부모를 연결해줍니다.

 

3. pq에서 하나씩 뽑으면서 a와 b 점의 부모가 같지 않다면 Union 해주시고, dist를 ans에 더해줍니다.

 

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
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
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
 
using namespace std;
 
struct node {
    int from;
    int to;
    double dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int N, M;
pair<int, int> arr[1001];
int vect[1001];
priority_queue<node, vector<node>, cmp> pq;
 
int Find(int a)        //부모 찾기
{
    if (vect[a] == a) return a;
    return vect[a] = Find(vect[a]);
}
 
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 = 1; i <= N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 1; i <= N - 1; i++) {        //모든 점 간의 거리를 기준으로 pq에 넣기
        for (int j = i+1; j <= N; j++) {
            ll x1 = arr[i].first;
            ll x2 = arr[j].first;
            ll y1 = arr[i].second;
            ll y2 = arr[j].second;
            double dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
            pq.push({ i,j,dist });
        }
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
    }
 
    double ans = 0;
 
    while (!pq.empty()) {
        int a = pq.top().from;
        int b = pq.top().to;
        double dist = pq.top().dist;
        pq.pop();
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans += dist;
        }
    }
 
    printf("%.2f", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 3584번 - 가장 가까운 공통 조상 (C++)  (0) 2022.11.18
[ 백준 ] 5529번 - 저택 (C++)  (0) 2022.11.17

+ Recent posts

티스토리툴바