[C++] 탑승구

1. 문제

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

2. 입력 조건

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

3. 출력 조건

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

4. 풀이

• 서로소 집합과 관련된 문제이다.
• 최대한 많은 비행기를 도킹시키려면 번호가 높은 쪽부터 채우는 것이 유리하다.
• 비행기가 도킹할 때마다 자신의 부모와 그 왼쪽 탑승구를 union연산을 해준다.
• union을 한 결과에 새로운 값을 넣으려고 할 때 그 번호의 부모가 0이 되면 새로운 값을 넣을 수 없고 도킹을 할 수 없다는 뜻이기 때문에 공항 운행을 종료한다.

5. 처음 코드와 달라진 점

• union을 root와 해주어야 하는데 그냥 현재 값으로 해주었다.
• 책의 정답에 있는 코드로 하면 값을 다 입력 받기 전에 도킹할 수 없으면 반복문이 종료해서 배열에 입력하고 다시 꺼내서 확인하는 식으로 수정했다.

6. 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int parent[100001];

int findParent(int x) {
  if(parent[x] == x) return x;
  else return findParent(parent[x]);
}

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if(a < b) parent[b] = a;
  else parent[a] = b;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>n>>m;

  for (int i = 0; i <= n; i++) {
    parent[i] = i;
  }

  vector<int> v;
  for (int i = 0; i < m; i++) {
    int x;
    cin>>x;
    v.push_back(x);
  }

  int answer= 0;
  for (int i = 0; i < m; i++) {
    int root = findParent(v[i]);
    if (root == 0) break;
    else {
      unionParent(root, root-1);
      answer++;
    }
  }
  
  cout<<answer;
}