프로그래밍/코딩테스트 문제풀이
[Python] 백준 10775. 공항
inspirit941
2019. 11. 12. 22:21
반응형
https://www.acmicpc.net/problem/10775
10775번: 공항
문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는
www.acmicpc.net
Union Find 문제.
문제를 Union find 형태로 풀어내는 방법은 https://mygumi.tistory.com/245
백준 10775번 공항 :: 마이구미
이 글은 백준 알고리즘 문제 10775번 "공항" 을 풀이한다. 문제 풀이는 유니온-파인드(union-find) 또는 디스조인트-셋(disjoint-set) 이라고 불리는 자료구조를 이용한다. 유니온-파인드 이해 - http://mygumi.ti..
mygumi.tistory.com
에서 상세하게 확인할 수 있다.
즉, 비행기를 도킹할수록 parent 값을 내려서, parent값이 0이 되면 반복문을 끝내고 도킹한 비행기 개수를 반환한다.
반응형