[그리디 알고리즘12] 백준 10775번 공항 파이썬

백준 10775 공항 

 

📜 문제 

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

 

 

🚩 입력 

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

 

 

 

🌞 출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

 

 

🥨문제 풀이 

Union-find 구조를 알아야 풀리는 문제이다. (사실 재귀, for, while도 되지만 시간 초과일 것 !) 

Union-find 문제를 한번 풀어보았지만 그래도 어렵게, 어렵게 이해했다. 사실 문제부터 이해가 어려웠다. 

문제의 내용은 게이트의 수 n 개, 비행기가 들어오는 수 p 그리고 들어오는 비행기가 4 라면 게이트 1~4까지 중 하나에 도킹할 수 있다는 내용같다. ( 정확히 이해하신분 댓글 부탁드립니다,! ) 

 

[4,1,1]

위와 같은 비행기 입장 array 에서 처음 들어오는 비행기는 1~4번 게이트 중 가장 큰 수인 4에 도킹을 시킨다. 확율적으로 4에 도킹을 시켜야 이 후에 1,2,3이 나오면 추가로 도킹을 시킬 수 있기 때문 

그리고 1번 비행기는 -> 1번 게이트에 도킹

그 다음 1번 비행기는 -> 1번 게이트에 도킹할 수밖에 없지만 이미 자리가 없으므로 도킹 최대 값은 2가 된다. 

 

시간초과가 나지않기 위해 Union-find 알고리즘을 사용하여 아래 코드처럼 풀 수 있다. 

 

 

 

 

🥕 정답 코드 

import sys
input = sys.stdin.readline
g = int(input())     # gate 수 
p = int(input())     # 비행기 수 
plane=[int(input()) for _ in range(p)]  # 비행기 들어오는 번호 List
parent={i:i for i in range(g+1)}        # 부모 노드를 찾기 위한 해시 -> {1:1, 2:2, 3:3...} <- 디폴트 값 

def find_parent(x):                # 순서 2 - plane 리스트의 각 요소를 x인자값으로 받는다. 
    if x == parent[x]:             # parent[x] 가 x 와 값이 같다면 = 아직 변동된 게 없다면 = ex) 3:3 이라면 
        return x                   # 바로 x 값을 주면 된다. (부모 노드가 본인 수와 동일)
    p = find_parent(parent[x])	   # 부모 노드가 본인의 수와 다르다면 부모 노드를 다시 find_parent함수를 돌려 부모노드의 부모 노드를 찾는다. (재귀) 
    parent[x] = p				   # parent[x]에 = (최종 부모의 노드 값) p 를 넣는다. 
    return p					   # p 를 return 한다.  

def union(x,y):							  # 순서 3 plane 요소의 부모 노드 값이 x 이고, y는 x-1이다.
    x = find_parent(x)					  # x 와 y  각각의 부모 노드를 찾는다. 
    y = find_parent(y)				      
    parent[x] = y                         # parent[x] = y    -   parent 해시 x 의 값을 y로 바꾸어 준다.  

c = 0 
for i in plane:                 # 순서 1  - plane 리스트 안의 각 요소에 for문을 돌린다. 	
    x = find_parent(i)			# x 에 find_parent(i) 의 값을 넣는다. find_parent는 부모 노드를 찾는 함수 
    if x==0: break              # 만약 부모 노드가 0 이라면 = 더이상 도킹할 곳이 없다. -> break 
    union(x,x-1)                # 0 이 아니라면 (부모노드를 함치는) union 함수에 x 와 x-1 값을 넣는다 
    c +=1					    # c 카운트를 세어준다. 
print(c)