[백준] 10775 공항

 

10775번: 공항

 

유니온 파인드를 이용해서 해결하는 문제이다. 유니온 파인드를 모른다면 검색해서 공부하고 글을 읽는 것을 추천한다.

원리는 다음 블로그를 참고하거나 "union find 최적화"로 검색하면 자료가 많이 나온다.

[자료구조]Union-Find: Disjoint Set의 표현

 

해당 문제를 보면 이것이 유니온 파인드를 이용한 문제라고 감이 잡히지 않았다. 그래서 문제를 보고 알맞은 알고리즘을 떠올리는 연습을 하기 위해서 문제를 분석해보았다.

 

1. 공항의 게이트를 최대한 활용하는 방법 찾기

공항의 게이트를 활용하기 위한 방법을 찾기 위해 비효율적으로 사용하는 방법을 생각해보았다. 

 

p : 공항의 게이트를 최대한 활용한다.

~p : 공항의 게이트를 최대한 활용하지 않는다.

 

q : 들어오는 비행기의 gi를 만족하는 게이트 중에서 가장 큰 게이트를 사용한다.

~q : 들어오는 비행기의 gi를 만족하는 게이트 중에서 가장 큰 게이트를 사용하지 않는다.

 

p <-> q 가 참이라면 q를 이용한 코드를 작성하면 된다. 다음 명제가 참임을 어떻게 증명할까?

 

p는 무조건 참이다. 왜냐하면 문제의 조건으로 인해 항상 참이다. p <-> q가 참이면 p<-> ~q는 거짓이다. p <-> ~q가 거짓임을 증명해보자.

 

비행기 2, 비행기 1이 순서대로 오는 상황을 상상하자.

 

처음으로 비행기 2가 1,2 게이트 중에서 가장 큰 게이트가 아닌 1을 선택하면 ~p 의 조건을 만족한다. 2를 선택하면 p를 만족하는 것이다. 그리고 비행기 1는 1 게이트를 무조건 사용해야 한다. 하지만  1게이트를 사용하고 있기에 공항은 닫는다. 반면 p를 만족하는 선택을 한 경우는 1게이트를 이용할 수 있다. ~p는 게이트 1개 사용을 했고 p는 게이트 2개 사용을 했다. 따라서 p<-> ~q는 거짓이다.

 

q와 유니온 파인드를 이용해서 문제를 풀면 해결할 수 있다.