[BOJ/백준] 10775 공항

import sys
input = sys.stdin.readline


G = int(input())
P = int(input())
result = 0
plane = [int(input()) for _ in range(P)]


parents_number = [i for i in range(G+1)]

visited = [False]*(G+1)
cur_idx = 0
planing = True

while cur_idx<P and planing:

    cur_plane_number = plane[cur_idx]
    check = [cur_plane_number]
    while visited[cur_plane_number] and cur_plane_number>0:
        cur_plane_number = parents_number[cur_plane_number]
        check.append(cur_plane_number)
    
    
    
    if cur_plane_number == 0:
        break
    else:
        visited[cur_plane_number] = True
        for num in check:
            parents_number[num] = cur_plane_number-1

    cur_idx += 1

print(cur_idx)

이 문제는 프로그래머스의 호텔 방 배정하기하고 동일한 문제라고 볼수 있다.

 

주어진 위치가 있고, 1~위치 사이에 비행기를 도킹할 수 없으면, 멈추면 되는것이다.

 

호텔 방 배정하기하고 동일하게, 자신의 다음 도킹 위치를 저장시켜놓으면 된다. 

 

그러면서 최악의 경우를 방지하기 위해, 그 다음 도킹위치를 새로 갱신해주는 작업을 해주면 된다.

 

import sys

input = sys.stdin.readline

def find_parent(idx):
    if idx == make_set[idx]:
        return idx
    else:
        make_set[idx] = find_parent(make_set[idx])
        return make_set[idx]

G = int(input())
P = int(input())

make_set = [i for i in range(G+1)]


result = 0
for k in range(P):
    plane_num = int(input())
    gate_num = find_parent(plane_num)

    if gate_num < 1:
        break
    else:
        make_set[gate_num] = make_set[gate_num-1]
        result += 1
        

print(result)

이거는 좀 더 함수로 만들어놓은 것이다.

 

위와 똑같은 로직이지만, find_parent 라는 재귀함수를 통해, 자동적으로 갱신이 되게 해주었다.

 

 

호텔 방 배정하기 문제를 수월하게 풀었으면 이 문제도 수월하게 풀 수 있을거라 생각한다.