[백준]10775 공항(Python)

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

10775번: 공항

 

문제 접근

 

우선 도킹이 무엇인가..? 처음엔 문제가 잘 이해가 되지 않았다..

1. 게이트가 4개 있고, 비행기 3대가 4, 1, 1 순으로 들어온다고 하면, 4와 1 최대 2대 도킹 가능

2. 게이트가 6개 있고, 비행기 6대가 2, 2, 3, 3, 4, 4 순으로 들어온다고 하면, 2, 3, 4 최대 3대 도킹 가능

 

근데 이게 유니온 파인드 문제라는 게 잘 와닿지 않았다.

 

코드 

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 게이트 개수
G = int(input())

# 비행기 개수
P = int(input())

# 부모 테이블
parents = [i for i in range(G+1)]

# 들어오는 비행기
plane = []

for _ in range(P):
    plane.append(int(input()))

count = 0

for k in plane:
    a = find_parent(k)
    # 더 이상 도킹 불가능
    if a == 0:
        break
    # 해당 게이트와 그 이전 번호의 게이트 연결 
    union_parent(a, a-1)

    count += 1

print(count)

 

참고

https://velog.io/@veonico/%EB%B0%B1%EC%A4%80-10775.-%EA%B3%B5%ED%95%AD-%ED%8C%8C%EC%9D%B4%EC%8D%ACpython

[백준] 10775. 공항 (파이썬/python)