본문 바로가기

ProgramSoliving

백준 : 10775

반응형

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

 

10775번: 공항

문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할

www.acmicpc.net

 

문제해결 방법 : Union-Find

이문제에서 생각할것은 도킹을 할수 없는 상태가 잇다면 그다음 쿼리는 처리안해주고 끝난다는 것이다.

두번째로는 gi 번째 게이트에 도킹한다고 과정할때 gi는 1~gi 까지 도킹 할 수 있는 가능성있다.

그 다음 쿼리가 또 gi를 한다면 처음 쿼리는 1~g(i-1) 번째로 도킹을 해야한다.

그 다음 쿼리가 또 gi 를 한다면 1번째와 2번째는 1~g(i-1) 를 서로 다른 게이트에 도킹햇어야한다.

문제를 이제생각해본다면 현재 gi 번째 게이트에 도킹 가능성만 판별하면 된다.

비행기가 순서대로 들어오기 때문에  1~ i-1 번째는 도킹이 되었다고 가정한다면  find(i) 를 하였을 경우 

0이 아닌값이 존재하는 것은 find(i)

Find 하엿을 경우 부모노드가 0이 아니라면 앞선 셋들을 어떻게든 배치하면 현재 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
import java.util.Scanner;
 
public class Main {
    static int G;
    static int P;
    static int g[];
    static int p[];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        G = sc.nextInt();
        P = sc.nextInt();
        g = new int[G + 1];
        p = new int[P];
        Init();
        int ans = 0;
        for (int i = 0; i < P; i++) {
            p[i] = sc.nextInt();
        }
 
        for (int i = 0; i < P; i++) {
            int next = Find(p[i]);
            if (next == 0) {
                break;
            } else {
                ++ans;
                g[next] = next - 1;
            }
        }
        System.out.println(ans);
 
    }
 
    public static int Find(int x) {
        if (x == g[x]) {
            return x;
        }
 
        int xx = Find(g[x]);
        return g[x] = xx;
 
    }
 
    public static void Init() {
        for (int i = 1; i <= G; i++)
            g[i] = i;
 
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
반응형

'ProgramSoliving' 카테고리의 다른 글

백준 16933: java  (0) 2020.04.30
백준 : 7682  (0) 2020.04.15
백준 : 1637  (0) 2020.04.15
백준 : 5213 JAVA  (0) 2020.03.17
백준 : 12886  (0) 2020.03.15