BOJ 10775 : 공항 (Python)

문제

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

10775번: 공항

 

 

코드

import sys
input = sys.stdin.readline

def find_parent(x):
    if parent[x] == x:
        return x
    P = find_parent(parent[x])
    parent[x] = P
    return parent[x]

def union(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

G = int(input())
P = int(input())

parent = {i: i for i in range(0, G+1)}
planes = []
count = 0

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

for plane in planes:
    x = find_parent(plane)

    if x == 0:
        break
    union(x, x-1)
    count += 1

print(count)

 

 

풀이

2중 반복문을 사용하니 시간초과가 따서 union-find를 사용해 풀었다. (2중 반복문 코드는 아래에)

 

1. find_parent(x)

def find_parent(x):
    if parent[x] == x:
        return x
    P = find_parent(parent[x])
    parent[x] = P
    return parent[x]

해당 원소의 부모를 찾는 함수로 재귀를 이용한다. 

 

 

2. union(x,y)

def union(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

x, y 모두 부모 원소를 찾아서 둘 중 더 작은 부모 원소를 따라간다. → 둘의 부모 원소가 같아진다  == 같은 합집합

 

아... 머리로는 이해가 되는 듯 한데 말로 설명을 못하겠다.. 그럼 전 이해를 덜한거겠죠... 

---

 

 

 

기타

우선 위 코드는 시간 초과가 나서 틀린 코드이나 아마 답을 출력하는데는 문제가 없을 것이다.

 

i 번째 비행기는 1번부터 gi 번째 게이트 중 하나에 영구적으로 도킹할 수 있다. 가능한 게이트의 수가 적은 비행기들(gi가 작을수록 게이트의 범위가 작아지므로 가능한 게이트의 수가 줄어든다.) 이 앞 쪽 게이트에 도킹할 수 있도록 양보하기 위해서 비행기는 gi번째 게이트부터 시작해서 1번째 게이트로 이동하면서 도킹이 가능한지 체크한 후 도킹할 수 있도록 한다. 

check 배열을 이용해서 게이트가 아직 도킹되지 않은 상태라면 0으로 표시한다.

도킹을 원할 시에

check 배열의 원소가 0 이라면 원소를 1로 바꾸고 (도킹되었다는 표시) result 값을 1증가한 후에 다음 비행기로 넘어간다.

check 배열의 원소가 1이라면 숫자가 더 작은 왼쪽 게이트로 이동하여 같은 과정을 반복한다.

 if maximum == 0:
        break

maximum 이 0이 될 때까지, 즉 gi번째부터 체크한 모든 게이트가 도킹이 돼있다면 공항은 폐쇄되므로 반복문을 종료하고 값을 출력한다.

 

 

코드

import sys
input = sys.stdin.readline

G = int(input())
P = int(input())
gate = [0] * P
check = [0] *(G+1)

for i in range(P):
    gate[i] = int(input())
    
result = 0

for i in range(P):
    maximum = gate[i]
    while maximum != 0:
        if check[maximum] == 0:
            check[maximum] = 1
            result += 1
            break
        maximum -= 1
    if maximum == 0:
        break
        
print(result)에 다음 비행기로 넘어간다.