[CCC] 탑승구

CCC 탑승구

그래프 / 서로소 집합

 

 

[문제]

 

 

 

[과정]

 

기본적으로 서로소 집합 문제

• 비행기 번호에 맞는 탑승구(루트)에 도킹
• 도킹할 수 없다면 비행기 번호 -1의 탑승구에 도킹 할 수 있는지 확인
• 탑승구(parent)가 0이 될 때까지 도킹하지 못하면 공항 운행을 중지시키고 도킹한 개수를 출력

 

 

[소스코드]

# 탑승구

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

g = int(input())
p = int(input())
parent = [0] * (g + 1)

for i in range(1, g+1):
    parent[i] = i

result = 0
for i in range(p):
    n = int(input())
    data = find_parent(parent,n)
    if data == 0:
        break
    union_parent(parent,data-1,n)
    result += 1
print(result)

 

---

 

[정답]