[Union-Find] 백준 10775 공항

 

 

문제링크 www.acmicpc.net/problem/10775

 

 

고통의 시간을 거치고 드디어 맞았다!! 🎉👏🎉👏

 

 

 

[답코드]

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6) # 최대 재귀 깊이 제한 늘림
 
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
 
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a):
    a = find_parent(parent, a)
    b = a-1
    if b<0:
        return -1
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    return 0
 
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v=int(input())
e=int(input())
parent = [0] * (v + 1) # 부모 테이블 초기화하기
 
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i
 
result=0
# Union 연산을 각각 수행
for i in range(e):
    a=int(input())
    if union_parent(parent, a)<0:
        break
    result += 1
 
print(result)

 

 

 

[풀이법]

 

① 최대 재귀 깊이 늘리기

파이썬은 재귀 호출 제한이 1000번까지라고 한다. 이를 늘려줘야 런타임 에러가 안 난다

 

 

 

 

② 흐름

 

입력값이 들어오면 union_parent를 진행한다.

입력값 a의 parent 노드를 찾아 (a의 parent노드)와 (a의 parent노드-1)을 합쳐준다

여기서 parent에 입력할 숫자의 범위는 0까지여야 하므로 b값이 0미만이면 break 한다

 

 

 

 

③ 출력(예제1)

 

입력값

4 3 4 1 1

 

초기화
입력 4, union(4, 3)
입력 1, union(1, 0)
입력 1, union(0, -1)	break *b가 0 미만

 

 

 

 

④ 출력(예제2)

입력값	4 6 2 2 3 3 4 4

 

초기화
입력 2, union(2, 1)
입력 2, union(1, 0)
입력 3, union(3, 1)
입력 3, union(0, -1)	break *b가 0 미만