공항 (10775번) - 백준 (BOJ)

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

10775번: 공항

 

 

백준 - 공항 (Gates) (10775번)

 

난이도 : Gold 2

알고리즘&자료구조 : Disjoint Set (서로소 집합) & Union Find (유니온 파인드)

 

---

 

< 전체 코드 >

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 9))


class Airport():
    def __init__(self, G, P):
        self.warp = [i for i in range(G+1)]
        for i in range(1, P+1):
            g = int(input())
            self.warp[g] = self._find(g)
            if self.warp[g] == -1:
                i -= 1
                break
        self.answer = i
        
    
    def _find(self, gate):
        if self.warp[gate] == gate:
            self.warp[gate] = gate-1
        else:
            self.warp[gate] = self._find(self.warp[gate])
        return self.warp[gate]
    

if __name__ == '__main__':
    port = Airport(int(input()), int(input()))
    print(port.answer)

 

 

---

 

★ [1 ~ g] gate에 도킹할 수 있는 비행기가 입력으로 들어왔을 때,

[1 ~ g] 에서 비어있는 gate 중 가장 큰 번호의 gate에 도킹시키는 것이 핵심 아이디어이다.

 

빈 gate 중 가장 큰 번호를 찾기 위해, union find 알고리즘을 활용할 수 있다.

 

 

 

① ( if : ) 만약 warp[gate] 값이 gate와 같다면,

gate 번 게이트는 비어있으므로, 그 자리에 도킹시킬 수 있다.

 

( else : ) 하지만 warp[gate] 값이 gate와 다르다면,

gate 번 게이트는 이미 다른 비행기가 도킹되어있다.

따라서, 다시 _find 함수를 통해 앞쪽에서 비어있는 가장 큰 게이트 번호를 찾는다. (recursion)

def _find(self, gate):
    if self.warp[gate] == gate:
        self.warp[gate] = gate-1
    else:
        self.warp[gate] = self._find(self.warp[gate])
    return self.warp[gate]

 

 

 

② 만약 warp[gate] 값이 -1이라면,

앞쪽에 도킹할 수 있는 빈 게이트가 없는 것이므로 탐색을 중단한다.

(현재 비행기 또한 도킹할 수 없으므로, i에서 1을 빼준다.)

if self.warp[g] == -1:
    i -= 1
    break

 

 

 

③ 현재까지 도킹시킨 비행기의 대수를 출력하면, 그것이 정답이 된다.

self.answer = i