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


처음에 단순히 dfs로 해결했습니다.

간단하지만 런타임 시간이 꽤 오래 걸리더군요.

일단 다 풀고나서 다른 분들이 어떻게 풀었나 봤더니


disjoint-set(union-find)로 푸셨더라구요!


그래서 저도 다시 풀어보았습니다.


간단했습니다. 우선 연결되어있다면 union을 해서 같은 그룹으로 묶습니다.

union을 한다고 모든 노드에서의 부모가 바뀌는 것은 아닙니다.

x와 y를 유니온 하면 x와 y의 부모만 바뀌는 것이므로

다시한번 find를 해줘야 완전히 갱신이 됩니다.

아무튼!! 이것은 union-find에 대해서 공부하시면 알게되실겁니다.


그리고 나서 모든 노드에 대해 그루핑이 끝났다면!


그룹이 몇개인지 세어줘야합니다!

저는 간단하게 노드 3천개에 대한 tmp 배열을 만들어서

해당 노드의 부모가 tmp배열에서 true라면 이미 센 그룹이므로 넘어가고 

false라면 안센 그룹이므로 tmp배열을 갱신시켜주고

그룹의 개수를 늘려줍니다.


uinon-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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
 
int parent[3000];
int n;
 
bool isConneted(int a, int b) {
    int x = pos[a].first - pos[b].first;
    int y = pos[a].second - pos[b].second;
    int z = r[a] + r[b];
 
    return (x * x + y * y) <= z * z;
}
 
int Find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
 
    if (x != y) {
        parent[x] = y;
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isConneted(i, j) && parent[i] != parent[j]) {
                    Union(i, j);
                }
            }
        }
 
        bool tmp[3000] = { 0, };
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            int p = Find(i);
            if (!tmp[p]) {
                tmp[p] = 1;
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
cs



dfs코드입니다.

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>
#include <vector>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
bool visit[3000];
int n;
 
int calcDistance(pii a, pii b) {
    int  x = (a.first - b.first);
    int y = (a.second - b.second);
    return x * x + y * y;
}
 
void dfs(int idx) {
    for (int i = 0; i < n; i++) {
        int rSum = r[idx] + r[i];
        if (idx == i || visit[i] || calcDistance(pos[idx], pos[i]) > rSum * rSum) continue;
        visit[i] = 1;
        dfs(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i);
                ret++;
            }
                
        }
        cout << ret << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2178] 미로 탐색  (0) 2017.09.15
[2667] 단지번호붙이기  (0) 2017.09.15
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


으악..한 10번 틀렸네요...

문제를 잘읽읍시다..!



블록친 부분을 굉장히! 아주 잘 읽으셔야합니다.


저는 저 부분을 안읽고.. 내가 내려갈떄 내리막길이면 올라올떈 오르막길이니 어느방향에서 접근하냐에 따라 달라질 것이라고 생각했습니다.


삐삐!!!!!!!!

아니였습니다.


이 문제는 그냥 연결해라!!!!!!!!!!!!! 이 문제였습니다...

네!

MST.. 최소 스패닝 트리로 해결하는 문제입니다.


저는 크루스칼로 해결했습니다.


MST에는 크루스칼과 프림이 있는데 MST를 잘모르시는 분들은

공부를 하고 문제를 해결하시기 바랍니당!


간단하게 설명해드리자면! 싸이클이 생기지 않고 정점 n개를 간선 n - 1개로 연결하는 방법입니당!


크루스칼에서는 disjoint-set 알고리즘이 사용됩니당!

성능을 위해서는 우선순위-큐를 사용하시면 더 도움이 됩니다.!


이 문제는 input에서 오르막길이 0으로, 내리막길이 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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 10000
#define MAX_SIZE 1001
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int parent[MAX_SIZE];
int n, m;
vector<pair<pii, int> > edge;
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[x] = y;
        return 1;
    }
 
    return 0;
}
 
int f(int mul) {
    priority_queue<pair<int, pii> > pq;
 
    for (int i = 0; i <= n; i++) parent[i] = i;
 
    for (int i = 0; i < edge.size(); i++) pq.push(mp(!edge[i].second * mul, mp(edge[i].first.first, edge[i].first.second)));
 
    int ret = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt <= n - 1) {
        int k = pq.top().first * mul;
        int from = pq.top().second.first;
        int to = pq.top().second.second;
        pq.pop();
 
        bool tmp = merge(from, to);
        if (tmp) {
            cnt++;
            ret += k;
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m + 1; i++) {
        int a, b;
        bool c;
        cin >> a >> b >> c;
 
        edge.push_back(mp(mp(a, b), c));
    }
 
    int best = f(-1);
    int worst = f(1);
 
    cout << worst*worst - best*best;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 최소 스패닝 트리(MST)' 카테고리의 다른 글

[1647] 도시 분할 계획  (0) 2017.08.30

+ Recent posts

티스토리툴바