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

[POJ/2431] Expedition

PS/etc.2018. 6. 27. 10:38

[2431] Expedition : http://poj.org/problem?id=2431


### Priority Queue ###


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct Exp { int dist, fuel; };
 
int n, L, P;
 
bool cmp(Exp a, Exp b)
{
    return L-a.dist < L-b.dist;
}
 
int main()
{
    scanf("%d", &n);
 
    vector<Exp> v;
    for(int i=0; i<n; i++) {
        int d, f;
        scanf("%d%d", &d, &f);
        v.push_back((Exp){d, f});
    }
 
    scanf("%d%d", &L, &P);
    sort(v.begin(), v.end(), cmp);
 
    int ans=0;
    int curL = P;
    priority_queue<int> pq;
 
    v.push_back((Exp){0, 0});
 
    for(int i=0; i<=n; i++) {
        while(L-v[i].dist > curL && !pq.empty()) {
            curL += pq.top(); pq.pop();
            ans++;
        }
        if(curL < L-v[i].dist) break;
        pq.push(v[i].fuel);
    }
 
    if(curL < L) ans = -1;
    printf("%d\n", ans);
    return 0;
}
 
cs

>> 34 번 라인이 없으면 틀렸다고 뜬다.

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

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[카카오 코드 / 예선] 카카오프렌즈 컬러링북  (0) 2018.05.04
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[카카오 코드 / 예선] 카카오프렌즈 컬러링북

PS/etc.2018. 5. 4. 13:31

[카카오 코드 / 예선] 카카오프렌즈 컬러링북 : https://programmers.co.kr/learn/courses/30/lessons/1829



<소스코드>


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
#include <vector>
 
using namespace std;
 
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int R, C;
 
bool safe(int r, int c)
{
    return (0 <= r && r < R) && (0 <= c && c < C);
}
 
int dfs(vector<vector<int>> &picture, int r, int c, int val)
{
    int ret = 1;
    picture[r][c] = 0;
    
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && picture[nr][nc]==val)
            ret += dfs(picture, nr, nc, val);
    }
    return ret;
}
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    R = m; C = n;
    
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(picture[i][j] != 0) {
                int tmp = dfs(picture, i, j, picture[i][j]);
                number_of_area++;
                if(max_size_of_one_area < tmp)
                    max_size_of_one_area = tmp;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}
cs


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

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[POJ/2431] Expedition  (0) 2018.06.27
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

<3-1> 나열하기 - 경우의 수

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

확인

티스토리툴바