[BOJ 10775] 공항

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

10775번: 공항

 

- 문제 요약

 

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려 한다.

비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

 

- 알고리즘 정리

 

Union-Find를 사용해서 풀었습니다.

현재 게이트가 도킹 가능한 게이트라면 바로 앞 게이트와 묶어줍니다.

도킹이 불가능한 게이트라면 현재까지 게이트에 도킹한 비행기의 수를 출력한 뒤 프로그램을 종료해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
int g,p,parent[MAX],a,result;
vector<int>v;

int Find(int x){
	if(parent[x]==x){
		return x;
	}
	return parent[x]=Find(parent[x]);
}

void Union(int x,int y){
	int fx=Find(x);
	int fy=Find(y);
	if(fx!=fy){
		parent[fy]=fx;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>g>>p;
	for(int i=1;i<=g;i++){
		parent[i]=i;
	}
	for(int i=0;i<p;i++){
		cin>>a;
		v.push_back(a);
	}
	for(int i=0;i<p;i++){
		int f=Find(v[i]);
		if(f!=0){
			Union(f-1,f);
			result++;
		}
		else{
			break;
		}
	}
	cout<<result;
}

코드 제출 결과