공항
-
백준 10775번 공항 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 00:34
이 글은 백준 알고리즘 문제 10775번 "공항" 을 풀이한다.문제 풀이는 유니온-파인드(union-find) 또는 디스조인트-셋(disjoint-set) 이라고 불리는 자료구조를 이용한다.유니온-파인드 이해 - http://mygumi.tistory.com/246문제 링크 - https://www.acmicpc.net/problem/10775 오늘은 신승원의 생일이다.박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착..