[백준 / BOJ] 10775 공항

문제

출처 : www.acmicpc.net/problem/10775

10775번: 공항

공항에 G개의 게이트가 있으며, P개의 비행기가 순서대로 들어온다.

각 비행기는 1~Pi번째 게이트에 도킹할수있으며, 만약 1~Pi번째 게이트가 다른비행기로 차있어 도킹하지못한다면, 공항이 폐쇄된다. 공항이 폐쇄되기 전까지 최대 몇개의 비행기를 도킹할수있는가 구하는 문제다.

 

풀이

유니온 파인드를 이용해 풀은 문제다.

 

비행기와 게이트가 최대 10만까지 갈수있으므로, 완전탐색으로 풀려할경우 NP번 반복하여 시간초과가 난다. 어떤 게이트에 비행기를 도킹시켜야하는지 찾아주는 연산을 유니온파인드를 이용해 최적화 시켰다.

 

문제를 보면, Pi비행기는 1~Pi번째 게이트까지 도킹할수있다 나와있다.

즉, 게이트의 번호가 작을수록 더 많은 비행기를 도킹시킬수 있다는뜻이고, 이를 통해 항상 최대한 높은번호의 게이트부터 도킹시키는게 이득이란걸 알수있다. 

 

매 탐색마다 도킹이 안되어있는 게이트중 최대한 높은번호의 게이트를 찾을려면 O(NP)번 반복하여 시간초과가 난다. 이를 빠르게 하기 위해 유니온 파인드를 사용해 경로를 압축시켰다. par[Pi] = Pi를 입력받았을때 연결할수있는 최대 게이트 와 같이 선언해서 풀었다.

 

예를들어, 문제의 예제 1을 보자.

예제1입력의 각 게이트 초기 연결 관계는 다음과 같이 표현할수있다.

par[i] = i // par[Pi] == 연결할수있는 최대 게이트

 

초기 연결관계 

par[1] = 1

par[2] = 2

par[3] = 3

par[4] = 4

 

4을 입력받은 후 연결관계

- par[4] = 4 이므로 4번 게이트에 비행기를 도킹시킨다. 더이상 4번게이트는 사용할수없으므로, 4번게이트를 입력받았을때, 3번게이트로 바로 이동시켜주기위해, par[4] = 3가 된다.

 

par[1] = 1

par[2] = 2

par[3] = 3

par[4] = 3

 

1을 입력받은 후 연결관계

- par[1] = 1 이므로 1번게이트에 비행기를 도킹시킨다. 마찬가지로 1번게이트는 사용할수없으므로, 1번게이트를 입력받았을때 종료시키기위해(1번보다 앞에있는 게이트는 없으므로..) par[1] = 0이 된다.

 

par[1] = 0

par[2] = 2

par[3] = 3

par[4] = 3

 

1을 입력받은후 연결관계

- par[1] = 0 이므로 공항을 폐쇠시키고, 지금까지 도킹한 비행기의 수 2를 출력한다.

 

종료

 

예제가 좀 작아 경로압축이 잘 안보여진거 같기 때문에 임의의 입력을 추가해보자.

 

세번째에 1이 아니라 4가 입력됐다고 가정하자.

ex)입력 : 4 3 4 1 4

- par[4] = 3 이므로 par[3]을 참조한다. 이때, par[3] = 3 이므로 3번게이트는 아직 사용할수있다. 3번게이트에 비행기를 도킹시키고 4 혹은 3을 입력받았을때, O(1)만에 찾아주기위해, par[4] = par[3] = par[2] 로 초기화 시켜준다.

 

par[1] = 0

par[2] = 2

par[3] = 2

par[4] = 2

 

 

이해가 잘 안되면 소스코드를 보도록하자.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10775%20%EA%B3%B5%ED%95%AD/main.cpp

devxb/JJUNalgo