[그리디/백준] 10775번: 공항, union-find 공부

-문제 : https://www.acmicpc.net/problem/10775

 

-정답 풀이 :

1번부터 비행기의 게이트 번호 중 빈 게이트에 넣는 것이라 이해해서 완전 탐색을 생각했지만, 이건 당연히 시간초과가 날 것 같아서 

다른 풀이를 시도했으나, 5%에서 계속 틀려서 구글링을 했다. 

찾아보니 union-find라는 개념을 이용하는데, 아직 정확히 이해가 가지 않았다. 

같은 부모(루트)에 대해서 연결하는 것 같은데 이 부분은 좀 더 공부해야할 것 같다 

 

아무튼 정답풀이

 

코드 참고한 블로그

설명 참고한 블로그 

import sys
input=sys.stdin.readline

answer=0
g=int(input())
p=int(input())
planes=[]
parent=[i for i in range(g+1)]

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

def find(x):
    if parent[x]==x:
        return x
    parent[x]=find(parent[x])
    return parent[x]

for plane in planes: #각 비행기의 게이트 번호
    docking=find(plane)
    if docking == 0: #도킹할 수 있는 게이트가 없는 경우
        break
    #해당 비행기와 게이트는 도킹했다는 것을 나타내기 위함
    parent[docking]=parent[docking-1]
    answer+=1
    
print(answer)

 

-삽질한 풀이;;

g=int(input())
p=int(input())
planes=[]
for _ in range(p):
    planes.append(int(input()))
planes=[0]+planes
visit=[0]*(g+1)
visit[0]=1
if g==1:
    print(1)
   
else:    
    i=1
    flag=False
    while True:
        if i==g:
            break
        for j in range(planes[i],-1,-1):
            if visit[j]==0:
                visit[j]=1
                flag=True
                break
        if not flag:
            break
        else:
            i+=1
       
    print(sum(visit)-1)