백준 10775번 공항 (Python)

백준 10775번 공항 (Python)

문제 링크

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

Test Case

문제 풀이

union-find문제 인데 완벽하게 이해를 하고 풀지는 못했다.

내가 확실히 이해한 부분은 g_i를 입력받았을 때 최대한 도킹을 많이 하기 위해서는 해당 번호의 게이트로 도킹하는 것이 제일 최선의 방법이라는 점이다.

처음에 문제만 봐서는 union-find 문제인지 알기어렵지만 문제 조건을 보면 G, P의 범위가 매우크기 때문에 일일히 확인하면서 빡구현하면 O(n^2)의 시간 복잡도를 가지게 된다.

0번 노드를 추가해야되는 점도 생각하지못했던 부분이다.

Source Code

import sys input = sys.stdin.readline def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a,b): a = find_parent(parent,a) b = find_parent(parent,b) if a > b: parent[a] = b else : parent[b] = a # 탑승구 g # 비행기 p g = int(input()) p = int(input()) data = [] for i in range(p): data.append(int(input())) parent = [0] * (g+1) for i in range(g+1): parent[i] = i result = 0 for i in range(p): root = find_parent(parent, data[i]) if root == 0 : break union_parent(parent,root, root-1) result += 1 print(result)

from http://minimun92.tistory.com/48 by ccl(A) rewrite - 2021-08-11 22:26:09