[Graph] 탑승구

탑승구

난이도 : 🌕🌕
푼횟수 : 🟡⚪⚪

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.
공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.
또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

입력 조건

• 첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어집니다.
• 둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어집니다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi (1 <= gi <= G)가 주어집니다. 이는 i번째 비행기가 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

출력 조건

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

입력 예시1
4
3
4
1
1

출력 예시1
2

입력 예시2
4
6
2
2
3
3
4
4

출력 예시2
3

입출력 예시에 대한 설명
첫 번째 예시에서는 2번 비행기 혹은 3번 비행기를 1번 탑승구에 도킹하고, 1번 비행기는 2번, 3번, 4번 탑승구 중 하나에 도킹할 때 최댓값을 가집니다.
두 번째 예시에서는 1번 비행기와 2번 비행기를 각각 1번 탑승구와 2번 탑승구에 도킹한 뒤에, 3번 비행기는 3번 탑승구에 도킹할 수 있습니다. 하지만 4번 비행기는 어떤 탑승구에도 도킹할 수 없기 때문에, 이 시점에서 공항의 운행이 중지됩니다.

나의 풀이

문제 해설

이 문제는 서로소 집합 알고리즘을 이용하면 효율적으로 해결할 수 있다. 각 탑승구를 서로 다른 집합으로 나타낸다고 해보자. 전체 탑승구가 4개(G = 4)일 때, 다음과 같이 그릴 수 있다. 초기 상태는 모두 루트 노트로 자기 자신을 가리키고 있다고 가정한다. 엄밀히 말하면 0번 탑승구는 존재하지 않지만, 문제 해결을 위해 0번 탑승구도 있다고 가정하자.

이때 비행기가 순서대로 들어오면 차례대로 도킹을 수행해야 하는데, 가능한 큰 번호의 탑승구로 도킹을 수행한다고 가정해보자. 이때 우리는 도킹하는 과정을 탑승구 간 합집합(union) 연산으로 이해할 수 있다. 새롭게 비행기가 도킹이 되면, 해당 집합을 바로 왼쪽에 있는 집합과 합친다. 단, 집합의 루트가 0이면, 더 이상 도킹이 불가능한 것으로 판단한다. 이러한 과정을 통해 문제를 해결할 수 있다.
예를 들어 문제의 ‘입력 예시 2’대로 비행기 정보가 입력된다고 하면, 다음과 같이 처리할 수 있다.

• 비행기 1
  첫 번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 2번 노드를 확인하는데, 현재 2번 노드의 루트는 2이다. 그러므로, 2번 노드와 1번 노드에 대하여 합집합 연산을 수행한다.

• 비행기 2
  두 번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 2번 노드를 확인하는데, 현재 2번 노드의 루트는 1번이다. 그러므로, 1번 노드와 0번 노드에 대하여 합집합 연산을 수행한다.

• 비행기 3
  세 번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 3번 노드를 확인하는데, 현재 3번 노드의 루트는 3이다. 그러므로, 3번 노드와 2번 노드에 대하여 합집합 연산을 수행한다.

• 비행기 4
  네 번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 3번 노드를 확인하는데, 현재 3번 노드의 루트는 0이다. 루트가 0이라는 점에서 더 이상 도킹을 할 수 없다는 의미이므로, 여기에서 마친다. 지금까지 총 3개의 비행기가 도킹되었으므로, 3을 출력하면 정답이다.
  따라서 이 문제는 이처럼 서로소 집합 자료구조를 이용하여 해결할 수 있다.

문제 답안

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
  # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[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 _ in range(p):
  data = find_parent(parent, int(input())) # 현재 비행기 탑승구의 루트 확인
  if data == 0: # 현재 루트가 0이라면, 종료
    break
  union_parent(parent, data, data - 1) # 그렇지 않다면 바로 왼쪽의 집합과 합치기
  result += 1

print(result)

기출 : CCC

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Algorithm 카테고리 내 다른 글 보러가기