(Week8)[서로소] 공항

 

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

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

10775번: 공항

• 문제를 이해하기가 좀 어려웠었는데, P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹... 부분을 제대로 이해하지 못했기 때문이었다. 
• 이를 다시 이해해보자면, 1번째 비행기가 4게이트에 할당된다면 1~4의 게이트 중 하나에만 도킹하면 되는 것이다.

2. 접근 방식

• 예제 1번의 경우 비행기가 [4, 1, 1] 순서라면 첫번째 비행기는 1~4번 게이트, 두번째 비행기는 1번 게이트, 세번째 비행기는 1번 게이트에 도킹할 수 있다.
• 따라서 높은 번호의 게이트에 접근할 수 있는 비행기들은 최대한 높은 번호의 게이트에 도킹해야 한다. 
• 따라서 첫번째 비행기는 4번 게이트에 도킹하고, 두번째 비행기는 1번 게이트에 도킹한다면, 세번째 비행기는 1번 게이트에 도킹할 수 없어서 거기서 종료가 된다.

따라서 위와 같이 문제를 이해한다면 서로소 알고리즘을 활용해서 루트 노드가 0을 가리키게 하면 된다. 처음에는 그냥 부모노드의 값을 -1씩 했는데 그렇게 하면 안된다. 서로소 알고리즘을 활용해야 하는 이유는 다음과 같은 경우 때문이라고 생각한다. 

•  첫번째 비행기가 4번 게이트에 도킹을 했다. (다음에 4번 게이트에 도킹하려는 비행기는 3번 게이트에 도킹해야 한다)
• 두번째 비행기가 3번 게이트에 도킹을 했다면, 다음 비행기는 2번 게이트에 도킹해야 한다.
• 다음으로 새번째 비행기가 4번 게이트에 도킹을 하려고 한다면, 첫번째 때문에 3번 게이트에 도킹해야 한다. 하지만 두번째 때문에 3번 게이트에도 도킹을 못한다. 따라서 2번 게이트에 도킹을 해야 한다. 

내 생각에는 위와 같은 상황 때문에 union_parent 연산이 필요하다고 생각한다. 게이트 3과 게이트 4의 parent를 union해줌으로써 모두 게이트 2를 가리킬 수 있도록 해야하기 때문에 서로소 알고리즘을 활용해야 한다. 

3. 코드

import sys # sys.stdin.readline
gate = [i for i in range(int(input())+1)]
plane = []
for i in range(int(input())):
    plane.append(int(input()))

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)
    parent[a] = b    
    
count = 0
for g in plane:
    x = find_parent(gate, g)
    if x == 0:
        break
    else:
        union_parent(gate, x, x-1)
        count += 1
print(count)

4. 코멘트

• 백준에서는 input이 많이 들어가는 경우 시간 효율성 문제가 생긴다. 따라서 sys 라이브러리의 stdin.readline함수를 사용해줘야 한다. 해당 문제에서도 그냥 input으로 하면 안되는 문제가 발생했다. 
• 코딩 스터디를 진행하면서 루트 노드를 부모 노드라고 얘기해서 전달에 오류가 생겼었다. 용어도 신경써서 얘기해야 한다.
• 백준 골드2짜리 문제였지만,  서로소 알고리즘을 이해했다면 쉽게 풀 수 있는 문제였다.
• 원래는 union_parent함수에서 조건문을 넣어줬었는데, 입력으로 들어오는 a, b의 순서가 항상 b가 a보다 작기 때문에 a의 부모노드로 b의 부모노드를 가리키기만 하면 된다. 따라서 조건문이 필요가 없어 뺐다.