알고리즘 :: 이것이 코딩 테스트다 :: 그래프 이론 문제 :: Q42 :: 탑승구

문제

G개의 탑승구와 P개의 비행기가 차례대로 도착하는 공항이 있다. P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나온다면 공항의 운행을 중지한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하시오.

문제접근

• 까다로운 문제다. 서로소 집합 유형이라는 것을 알아도 풀이과정을 떠올리기 쉽지 않다.
  N=100,000이므로 $O(n^2)$ 풀이법은 사용할 수 없다.

1. 서로소 집합 문제가 그러하듯, 부모 테이블을 자기 자신으로 초기화 한다.
2. 비행기 번호를 입력받으면 그 번호의 root 번호를 찾는다.
3. root 번호와 root 번호 - 1을 union()연산 한다.
4. 만일 root 번호가 0이라면 있을 수 없는 경우이자 도킹이 불가능한 경우이므로 공항 운행을 중단한다.

코드

$O(n^2) 풀이 (\ 잘못된\ 풀이\ )$

#include <iostream>
using namespace std;

static int G, P;
static bool entrance[100001];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> G >> P;

    bool opFlag = true;
    int answer = 0;
    for (int i = 0; i < P; ++i) {
        int planeNum;   cin >> planeNum;
        if(opFlag){
            bool flag = false;
            for (int j = planeNum; j > 0; --j)
                if (entrance[j] == false) {
                    entrance[j] = true;
                    flag = true;
                    answer++;
                    break;
                }
            if (!flag) opFlag = false;
        }
    }
    cout << answer << '\n';
}

정상 풀이

#include <iostream>#
using namespace std;
 
static int G, P, rootInfo[100001];
 
int findOperation(int x) {
	if (rootInfo[x] != x) return findOperation(rootInfo[x]);
	return rootInfo[x];
}
 
void unionOperation(int lhs, int rhs) {
	lhs = findOperation(lhs), rhs = findOperation(rhs);
	(lhs < rhs) ? (rootInfo[rhs] = lhs) : (rootInfo[lhs] = rhs);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> G >> P;
	for (int i = 1; i <= G; ++i) rootInfo[i] = i;
 
	int answer = 0;
	for (int i = 0; i < P; ++i) {
		int inputNum = 0;	cin >> inputNum;
		int rootOfInputNum = findOperation(inputNum);
		if (rootOfInputNum == 0) break;
		unionOperation(rootOfInputNum, rootOfInputNum - 1);
		answer++;
	}
	cout << answer << '\n';
}

결과

4
6
2
2
3
3
4
4

3