짱아의 개발 기록장

백준 10775번. 공항(c++) / 유니온파인드 본문

Algorithm/Baekjoon

백준 10775번. 공항(c++) / 유니온파인드

jungahshin 2020. 8. 31. 18:35
반응형

아이디어가 생각나지 않아 다른 분의 아이디어를 참고하여 유니온파인드로 구현했다.

 

핵심 아이디어는 3번 게이트로 들어오게 되면, 3->2를 가리키도록 union해주어야 한다.

따라서, 다시 한 번 3번 게이트로 다른 비행기가 들어오면 바로 3의 Parent인 2에 넣어줄 수 있게 된다.

만약 Parent값이 게이트 범위 안에 있지 않다면, 바로 공항은 폐쇄된다.

 

 

코드 첨부

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
// 공항
#include <iostream>
#include <vector>
using namespace std;
 
int g, p, n;
vector<int> airplane;
int num = 0;
int connect[100001= {0, }; // 유니온파인드
 
int find(int x){
    if(connect[x] == x){
        return x;
    }else{
        return connect[x] = find(connect[x]);
    }
}
 
int main()
{
    cin>>g>>p;
    for(int i=1; i<=g; i++){
        connect[i] = i;
    }
    for(int i=0; i<p; i++){
        cin>>n;
        airplane.push_back(n);
    }
 
    for(int i=0; i<airplane.size(); i++){
        int a = find(airplane[i]);
        if(1<=&& a<=g){
            // a와 a-1을 연결해준다.
            connect[a] = a-1;
            num++;
        }else{
            break;
        }
    }
    
    cout<<num<<"\n";
    return 0;
}
cs

 

문제 첨부

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

 

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불��

www.acmicpc.net

반응형
Comments