백준 10775: 공항

문제

풀이

입력 게이트 번호 : a
1~a의 게이트 중에 가장 큰 번호의 게이트부터 도킹을 하기 위해
find로 도킹 가능한 가장 큰 번호의 게이트 번호를 찾는다.
0일 경우 가능한 게이트가 없으므로 종료.
0이 아닐 경우 도킹 가능한 가증 큰 번호 게이트-1과 a를 union 해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    static int  g,p;
    static int[] group;		//union-find를 위한 배열

    public static void main(String args[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        g=Integer.parseInt(br.readLine());
        p=Integer.parseInt(br.readLine());
        group=new int[g+1];
        for(int i=1;i<g+1;i++)group[i]=i;
        int ans=0;
        
        for(int i=0;i<p;i++){
            int a=Integer.parseInt(br.readLine());
            if(find(a)!=0){
                union(find(a)-1,a);
                ans++;
            }
            else break;
        }
        System.out.println(ans);
    }

    static int find(int x){
        if(x!=group[x]){
            group[x]=find(group[x]);
        }
        return group[x];
    }

    static void union(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return;
        group[b]=a;
    }
}

#union-find