[java 백준] 10775번 공항

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
 
    public static int G;
    public static int P;
 
    public static int res=0;
 
    public static int parents[];
 
    public static int find(int a){
        if(parents[a]!=a){
            parents[a]=find(parents[a]);
        }
 
        return parents[a];
    }
 
    public static void union(int a,int b){
 
        a=find(a);
        b=find(b);
 
        if(a<b){
            parents[b]=a;
        }else{
            parents[a]=b;
        }
 
    }
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        G=Integer.parseInt(br.readLine());
        P=Integer.parseInt(br.readLine());
        parents=new int[G+1];
        for(int i=0;i<=G;i++){
            parents[i]=i;
        }
        
        //도킹할 때 union이 실행되어야 함
        //도킹할 수 있는 가장 큰 게이트에 먼저 도킹을 해준다. (합치는건 작은쪽으로 해야함! 원래 하던대로)
        //union이라는건 노드들이 가리키는 부모를 통일한다.
        // 부모노드가 0이면 더이상 도킹할 게이트가 없다는 의미임
 
 
        for(int i=0;i<P;i++){
            int gate=Integer.parseInt(br.readLine());
 
            if(find(gate)==0){
 
 
               break;
            }
            res++;
            union(find(gate),find(gate)-1); //들어갈 수 있는 가장 큰 게이트를 먼저 도킹해주고 왼쪽에 있는 노드와(하나 작은 게이트) 합집합 연산
 
        }
        System.out.println(res);
 
        
 
 
 
 
 
 
 
    }
 
}

 

같은 집합에 있는가는 부모노드가 같냐라고 생각해 볼 수 있다. 

비행기를 최대 몇대 도킹할 수 있는가는 반대로 비행기를 언제 도킹할 수 없을까? 에 대해서 생각해볼 수 있다.

비행기가 도킹할 수 없을 때는 더이상 들어갈 수 있는 게이트가 없을 때이다. 

그러면 루트노드가 0일때 게이트에 들어갈 수 없다고 생각해보자.

 

내가 들어갈 수 있는 게이트 중 가장 큰 게이트를 먼저 도킹하고 거기서부터 하나 작은 게이트와 합집합 연산을 진행해서 루트 노드를 줄여나가다가 결국 루트 노드가 0이되면 게이트에 들어갈 수 없게 되고 그 횟수를 센것이 '비행기를 최대 몇개 도킹할 수 있느냐'가 될 것이다. 

 

다시 처음으로 돌아가서 결국에 같은 집합이라는 것은 도킹을 한 애들을 모아놓은 것이라 생각하면 될듯하다!

 

아 그리고 중요한 부분이

union(find(gate),find(gate)-1); 

 

여기인데 그래야 부모노드를 좁혀나가면서 생각할 수 있다. 예를 들어 2번째 테스트케이스를 보면

2

2

3

3

4

4

가 나온다. 그러면 첫번째 비행기는 union(2,1)을 하면서 2번째 노드와 1번째 노드를 합쳐준다.

근데 두번째 비행기는 이미 2번째 노드의 부모노드가 1이기에 union(1,0)을 해야하는데 

만약 union(gate,gate-1)을 하면 union(2,1)을 한번 더 해주는 거기에 부모노드를 찾는 과정에 아무런 도움이 되지 않는다! 

 

구글링해보니까 이런문제를 "경로압축"이라고 불렀다. 최상단의 노드를 부모노드라고 생각하는 것이다. 여기선 루트노드가 0일때 이다. 

https://lemonlemon.tistory.com/124