[BOJ] 10775. 공항

유니온파인드를 이용하는 문제이다.

프로그래머스의 호텔방배정과 상당히 유사한 문제이다. 다만 이문제는 이하를 찾는점이 앞의 문제와 다른점이다. 비행기의 번호가 들어오면 그 비행기의 부모를 찾아주고, 그찾은 부모와 하나 부모이하를 union해주는 과정을 거친다. 만일 비행기의 부모가 0이 오면 더이상 추가할수가 없다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_10775_공항 {
    static int[] p;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int G=Integer.parseInt(br.readLine());
        p=new int[G+1];
        for(int i=1;i<=G;i++)
            p[i]=i;
        
        int airplane=Integer.parseInt(br.readLine());
        int answer=0;
        
        for(int i=0;i<airplane;i++) {
            int num=Integer.parseInt(br.readLine());
            int place=find(num);
            
            if(place!=0) {
                union(place-1,place);
                answer+=1;
            }
            else {
                break;
            }
    
        }
        System.out.println(answer);
    }
    
    static int find(int num) {
        if(p[num]==num)
            return num;
        
        return p[num]=find(p[num]);
    }
    
    static void union(int num1,int num2) {
        num1=find(num1);
        num2=find(num2);
        
        if(num1<num2)
            p[num2]=num1;
        else if(num1>num2)
            p[num1]=num2;
    }
}