Q42. 탑승구
🐣문제
공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.
공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째(1<=gi<=G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.
또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.
입력 조건
첫째 줄에는 탑승구의 수 G가 주어집니다.
둘때 줄에는 비행기의 수 P가 주어집니다.
다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi가 주어집니다. 이는 i번째 비행기가 1부터 gi번째 (1<=gi<=G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.입력 예시
4
3
4
1
1
출력 조건
첫째 줄에 도킹할 수 있는 비행기의 최대 수를 출력합니다.출력 예시
2
🐥풀이
풀이과정만 이해하면 나름 수월했다 ㅎㅁㅎ
비행기가 도킹할 수 있는 최대 탑승구에 도킹해간다. 도킹했으면, 최대 도킹 수를 줄인다.진짜 말로 설명하기도 힘들고 이해하기도 힘들다@! 그림으로 보자!
입력값으로 각 비행기가 도킹할 수 있는 최대 탑승구의 정보가 들어온다. 예를 들어 한 비행기는 입력값을 4로 받았다고 하자. 1번부터 4번까지의 탑승구에 도킹할 수 있다.
비행기를 최대 수로 도킹해야하므로, 도킹할 수 있는 최대 번호의 탑승구에 도킹시키는 것이 유리하다. 따라서 탑승구의 정보를 4로 받은 비행기를 탑승구 4에 도킹시켰다. 그럼 앞으로의 비행기들은 4번 탑승구에 도킹 가능해도 자리가 없어서 도킹할 수 없다. 그래서 탑승구 4번의 루트 번호를 한칸 줄어든 3으로 업데이트 시켜준다. 그러면 똑같이 4번 탑승구까지 도킹할 수 있는 비행기는 탑승구 3번으로 도킹할 것이다.
요약하면, 그래프 이론 알고리즘을 사용한다. 도킹 가능한 탑승구의 번호를 루트로 취급하여 알고리즘을 세워나간다.
🐓코드
# 입력값
n = int(input())
p = int(input())
plane = [int(input()) for _ in range(p)]
# 그룹 초기화
team = [0]*(n+1)
for i in range(1,n+1): team[i]=i
# 루트 찾기
def find_root(team, x):
if team[x]!=x:
return find_root(team,team[x])
return team[x]
# 팀 합치기
def union_team(team, a, b):
a = find_root(team, a)
b = find_root(team, b)
if a<b:
team[b]=a
else:
team[a]=b
count = 0
for p in plane:
root = find_root(team, p)
# 탑승구 루트가 0이면 더 못들어가므로 break
if root==0:
break
# 탑승구 최대 번호에 도킹하고, -1만큼 작은 탑승구를 root로
union_team(team, root, root-1)
count += 1
print(count)⭐2022.05.12
처음에 문제를 봤을 때는 이게 왜 그래프 이론이지.. 했는데 풀이를 보고 도킹 가능한 탑승구를 루트로 보고 풀이를 풀어나가는 것을 보고 너무너무 신기했다.. ㅇㅁㅇ!! 댑악
