How We Coding

[POJ/1182] 먹이 사슬

PS/etc.2018. 7. 25. 14:09

### Union Find ###


- Union-Find 는 같은 그룹을 관리하는 자료구조.


[1182] 먹이사슬 : http://poj.org/problem?id=1182


- 이 문제의 경우, 같은 종류인지만 판단하는 것이 아니라 "먹는다" 라는 관계가 포함되어 있다.


- 각 동물 i에 대해 3개의 요소 i-A, i-B, i-C 를 만들어 3*n 개의 요소로 Union-Find 를 만든다.

- i-X 는 i가 종류 x인 경우를 표현한다.


- t == 1 : X Y가 같은 종류로, [X-A, Y-A] [X-B, Y-B] [X-C, Y-C] 의 3개의 페어를 유니온한다.

>> 모순이 발생하는지 확인하려면, [X-A, Y-B] 가 유니온 되어 있는지 확인하면 된다.


- t == 2 : X 가 Y를 먹는다. [X-A, Y-B] [X-B, Y-C] [X-C, Y-A] 의 3개의 페어를 유니온한다. 

>> 모순이 발생하는지 확인하려면, [X-A, Y-A] 가 유니온 되어 있는지 확인하면 된다.

referenced by 노란책.

<소스코드>

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
#include <stdio.h>
 
int n, k;
int p[500001*3];
 
int safe(int x)
{
    return (0 <= x && x < n);
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
int same(int x, int y)
{
    x = find(x);
    y = find(y);
    return x == y;
}
 
void Union(int x, int y)
{
    x = find(x);
    y = find(y);
    p[x] = y;
}
 
int main()
{
    int ans=0;
    scanf("%d%d", &n, &k);
 
    for(int i=1; i<=n*3+1; i++) 
        p[i] = i;
 
    while(k--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        x--; y--; // [0, n)
 
        if(!safe(x) || !safe(y)) ans++;  
        else {
            if(t == 1) { // x == y
                if(same(x, y+n) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y);
                    Union(x+n, y+n);
                    Union(x+2*n, y+2*n);
                }
            }
            else { // x > y
                if(same(x, y) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y+n);
                    Union(x+n, y+2*n);
                    Union(x+2*n, y);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 예를들어 설명하면, N=100 인 경우를 생각해보자.

1) 1과 2가 같은 종류라면, Union(1, 2), Union(101, 102), Union(201, 202) 가 진행된다.

2) 1이 2를 잡아먹는다면, Union(1, 102], Union(101, 202), Union(201, 2) 가 진행된다.


1) t == 1 은 x 와 y가 같은 종류인지 묻는 상태.

>> same(x, y*n) 은 x가 y를 잡아먹는 관계인지 확인.

>> same(x, y*2*n) 은 y가 x를 잡아먹는 관계인지 확인하는 케이스이다. (58라인 참고)


2) t==2 인경우는 x가 y를 잡아먹는지 묻는 상태.

>> same(x, y) 는 x가 y와 같은 종류인지 확인

>> same(x, y+2*n) 은 y가 x를 잡아먹는지 확인

'PS > etc.' 카테고리의 다른 글

[POJ/2431] Expedition  (0) 2018.06.27
[카카오 코드 / 예선] 카카오프렌즈 컬러링북  (0) 2018.05.04
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[13424] 비밀 모임

BOJ/Shortest Path2018. 7. 24. 16:29

### Dijkstra or Floyd ###


[13424] 비밀 모임 : http://boj.kr/13424



<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF=1e9;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, m;
        scanf("%d%d", &n, &m);
 
        vector<P> g[101];
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            g[b].push_back(P(a, c));
        }
        
        int k, f;
        scanf("%d", &k);
        
        vector<int> ans(n+1, 0);
        for(int i=0; i<k; i++) {
            scanf("%d", &f);
            vector<bool> visited(n+1);
            vector<int> dist(n+1, INF);
            dist[f] = 0;
 
            priority_queue<P> pq;
            pq.push(P(0, f));
 
            while(!pq.empty()) {
                int cur;
                do {
                    cur = pq.top().second;
                    pq.pop();
                } while(!pq.empty() && visited[cur]);
 
                if(visited[cur]) break;
                visited[cur] = 1;
 
                for(auto &p : g[cur]) {
                    int next = p.first;
                    int d = p.second;
                    if(dist[next] > dist[cur] + d) {
                        dist[next] = dist[cur] + d;
                        pq.push(P(-dist[next], next));
                    }
                }
            }
            for(int i=0; i<=n; i++) {
                ans[i] += dist[i]; 
            }
        }
 
        int idx=1, minD=INF; 
        for(int i=1; i<=n; i++) {
            if(minD > ans[i]) {
                minD = ans[i];
                idx = i;
            }
        }
        printf("%d\n", idx);
    }
}
 
 
cs


>> 더 빠른시간에 수행된 다른사람들의 코드를 보니 플로이드로 풀었다.

>> n 제한이 100이라 플로이드로 돌려도 된다고 생각했지만, 다익스트라 공부중이라 다익스트라로 품

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[10282] 해킹  (0) 2018.07.24

[10282] 해킹

BOJ/Shortest Path2018. 7. 24. 15:22

### Dijkstra ###


[10282] 해킹 : http://boj.kr/10282


<소스코드>


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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli INF = 1e15;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, d, c;
        scanf("%d%d%d", &n, &d, &c);
 
        vector<P> g[10001];
        for(int i=0; i<d; i++) {
            int a, b, s;
            scanf("%d%d%d", &a, &b, &s);
            // a 가 b를 의존
            // b 가 감염되면 s초 후에 a도 감염.
            g[b].push_back(P(a, s));
        }
    
        priority_queue<P> pq;
        pq.push(P(0, c)); 
 
        vector<bool> visited(n+1);
        vector<lli> dist(n+1, INF);
        dist[c] = 0;
 
        while(!pq.empty()) {
            int cur;
            do {
                cur = pq.top().second;
                pq.pop();
            } while(!pq.empty() && visited[cur]);
 
            if(visited[cur]) break;
            visited[cur] = 1;
            
            for(auto &p : g[cur]) {
                int next = p.first;
                int d = p.second;
                if(dist[next] > dist[cur] + d) {
                    dist[next] = dist[cur] + d;
                    pq.push(P(-dist[next], next));
                }
            }
        }
 
        int cnt=0, time=0;
        for(int i=1; i<=n; i++) {
            if(dist[i] != INF) {
                cnt++;
                if(time < dist[i])
                    time = dist[i];
            }
        }
        printf("%d %d\n", cnt, time);
    }
    return 0;
}
 
 
cs

>> 

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[13424] 비밀 모임  (0) 2018.07.24

티스토리툴바