반응형

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

 

3780번: 네트워크 연결

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언하고, vect[ i ] = i로 초기화합니다.

 

2. I 커맨드를 입력 받을 때마다 I와 J를 연결해 주고, dist[ I ] = abs(I - J) % 1000으로 갱신해 줍니다.

 

3. E 커맨드를 입력받을 때마다 Find 함수를 통해 부모 노드를 찾아주고, 각 노드에서 부모 노드까지의 거리를 dist[ num ] 에 저장해 줍니다.

 

4. dist[ I ]를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int T, N;
int vect[20001];
int dist[20001];
 
pair<int,int> Find(int num)
{
    if (vect[num] == num) return make_pair(num, dist[num]);
    pair<int,int> temp = Find(vect[num]);
    vect[num] = temp.first;
    dist[num] += temp.second;
    return make_pair(vect[num], dist[num]);
}
 
void Union(int I, int J)
{
    vect[I] = J;
    dist[I] = abs(J - I) % 1000;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
            dist[i] = 0;
        }
 
        while (1) {
            char cmd;
            cin >> cmd;
 
            if (cmd == 'E') {
                int I;
                cin >> I;
                Find(I);
 
                cout << dist[I] << '\n';
            }
            else if (cmd == 'I') {
                int I, J;
                cin >> I >> J;
 
                Union(I, J);
            }
            else break;
        }
    }
}
cs
반응형
반응형

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

 

2463번: 비용

첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. vect[ i ] = i, cnt[ i ] = 1로 초기화하고, 모든 간선의 길이를 더해 sum에 저장합니다.

 

3. 모든 간선을 저장할 arr 배열을 선언하고, 간선의 길이를 기준으로 내림차순으로 정렬합니다.

 

4. for문으로 arr 배열을 돌면서 Union-Find를 이용하여 노드들이 연결될 때마다 ans에 sum을 더해주고, sum에서 간선의 길이를 빼줍니다.

 

5. ans % 1,000,000,000을 출력해줍니다.

 

[ 소스코드 ]

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>
#define ll long long
 
using namespace std;
 
struct edge {
    int u, v, c;
};
 
int N, M;
edge arr[100000];
int vect[100001];
int cnt[100001];
 
bool cmp(edge left, edge right)
{
    return left.c > right.c;
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = vect[a];
    int pb = vect[b];
 
    vect[pb] = pa;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    ll sum = 0;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        arr[i] = { u,v,c };
 
        sum += c;
    }
 
    sort(arr, arr + M, cmp);
 
    ll ans = 0;
 
    for (int i = 0; i < M; i++) {
        const int u = arr[i].u;
        const int v = arr[i].v;
        const int c = arr[i].c;
 
        if (Find(u) != Find(v)) {
            ans += sum * cnt[Find(u)] * cnt[Find(v)];
            Union(u, v);
        }
 
        sum -= c;
    }
 
    cout << ans % 1000000000;
}
cs
반응형
반응형

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

 

17398번: 통신망 분할

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

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

 

3. 끊을 연결들을 stack에 저장합니다.

 

4. 끊을 연결들을 제외하고 나머지 연결들을 Union-Find를 이용하여 연결해 줍니다.

 

5. 끊을 연결들을 stack에서 하나씩 빼서 연결해 주면서 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
#include<iostream>
#include<stack>
#define ll long long
 
using namespace std;
 
int N, M, Q;
int visited[100001];
int vect[100001];
ll cnt[100001];
pair<intint> arr[100001];
stack<int> edge;
 
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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    scanf("%d %d %d"&N, &M, &Q);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d"&arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < Q; i++) {
        int A;
        scanf("%d"&A);
        edge.push(A - 1);
        visited[A - 1= 1;
    }
 
    for (int i = 0; i < M; i++) {
        if (visited[i] != 1) {
            if (Find(arr[i].first) != Find(arr[i].second)) {
                Union(arr[i].first, arr[i].second);
            }
        }
    }
 
    ll ans = 0;
 
    while(!edge.empty()){
        int a = arr[edge.top()].first;
        int b = arr[edge.top()].second;
        edge.pop();
 
        if (Find(a) != Find(b)) {
            ans += (cnt[Find(a)] * cnt[Find(b)]);
            Union(a, b);
        }
    }
 
    printf("%lld\n", ans);
}
cs
반응형
반응형

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

 

18116번: 로봇 조립

성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 cnt 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. cnt 배열을 모두 1로 초기화하고, vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 cnt 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int vect[1000001];
int cnt[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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    
    for (int i = 1; i < 1000001; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < N; i++) {
        char cmd;
        cin >> cmd;
 
        if (cmd == 'I') {
            int a, b;
            cin >> a >> b;
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
        }
        else {
            int a;
            cin >> a;
 
            cout << cnt[Find(a)] << '\n';
        }
    }
}
cs
반응형
반응형

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

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 rel 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. unordered_map 자료 구조를 활용하여 해당 친구의 인덱스를 저장합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 rel 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#include<string>
 
using namespace std;
 
int vect[200001];
int rel[200001];
unordered_map<stringint> m;
 
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;
    rel[pa] += rel[pb];
}
 
int main()
{
    int T;
    scanf("%d"&T);
 
    for (int t = 0; t < T; t++) {
        int F;
        int cnt = 1;
        m.clear();
        scanf("%d"&F);
 
        for (int i = 1; i <= F * 2; i++) {
            vect[i] = i;
            rel[i] = 1;
        }
 
        for (int i = 0; i < F; i++) {
            char A[21];
            char B[21];
            scanf("%s %s", A, B);
 
            if (m.count(A) == 0) {
                m[A] = cnt++;
            }
            if (m.count(B) == 0) {
                m[B] = cnt++;
            }
 
            int a = m[A];
            int b = m[B];
 
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
 
            printf("%d\n", rel[Find(a)]);
        }
    }
}
cs
반응형
반응형

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

 

11085번: 군사 이동

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vect[ p ] 배열을 만들어 각 지점의 부모 노드를 저장합니다.

 

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int start;
    int end;
    int width;
};
 
bool cmp(node left, node right) {
    return left.width > right.width;
}
 
int p, w, c, v;
node arr[50000];
int vect[1000];
 
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 %d"&p, &w, &c, &v);
 
    for (int i = 1; i < p; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < w; i++) {
        int s, e, w;
        scanf("%d %d %d"&s, &e, &w);
        arr[i] = { s,e,w };
    }
 
    sort(arr, arr + w, cmp);
 
    int ans = 1000;
 
    for (int i = 0; i < w; i++) {
        const int a = arr[i].start;
        const int b = arr[i].end;
        const int width = arr[i].width;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans = min(ans, width);
 
            if (Find(c) == Find(v)) {
                printf("%d", ans);
                return 0;
            }
        }
    }
}
cs
반응형
반응형

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

 

16562번: 친구비

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 친구비를 입력받고, 이 값을 priority_queue에 친구비와 친구의 번호를 넣습니다.

 

2. 이미 친구인 번호를 입력받고, 이를 Union-Find를 통해 연결 관계를 저장합니다.

 

3. 나와 친구가 되면 0과 연결하고, 친구가 될 때 친구비를 ans에 저장합니다.

 

4. 총 친구비 ans가 k를 넘어서면 Oh no를 출력하고, 그렇지 않다면 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>
#include<queue>
 
using namespace std;
 
int N, M, k;
int arr[10001];
int vect[10001];
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
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);
    priority_queue<pair<intint>vector<pair<int,int>>, greater<pair<int,int>>> pq;
 
    for (int i = 1; i <= N; i++) {
        scanf("%d"&arr[i]);
        pq.push({ arr[i], i });
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int v, w;
        scanf("%d %d"&v, &w);
        if (Find(v) != Find(w)) {
            Union(v, w);
        }
    }
 
    int ans = 0;
 
    while (!pq.empty()) {
        const int cost = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (Find(cur) != 0) {
            Union(0, cur);
            ans += cost;
        }
    }
 
    if (ans > k) {
        printf("Oh no");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
반응형

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

+ Recent posts