백준 Gold 2 공항

공항 (백준 Gold 2)

https://www.acmicpc.net/problem/10775

‘게이트’와 ‘비행기 개수’가 각각 주어진다
이후 도착하는 ‘비행기’의 번호가 주어질때
가능한 도킹할 수 있는 개수는 문제

풀이 방법

• 비행기가 가능한 ‘자기 자신’의 번호부터
  1까지 탐색하며 가능한 도킹 가능한지를 판별
  

• 도킹 불가능하면 즉시 종료
  

첫 제출 코드

#include<iostream>
#include<memory.h>

using namespace std;

int g, p;

int main()
{
	cin >> g >> p;
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int* airports = new int[100002];
	memset(airports, 0, sizeof(int) * 100002);
	int answer = 0;

	for (int i = 1; i <= p; i++)
	{
		int t;
		cin >> t;
		
		bool isSet = false;

		for (int j = t; j >= 1; j--)
		{
			if (airports[j] == 0)
			{
				airports[j] = i;
				isSet = true;
				break;
			}
		}

		if (isSet)
			answer++;
		else
			break;
	}

	cout << answer;

	delete[] airports;

	return 0;
}

시간초과?

기본적으로 현재 코드가
‘자기 자신의 번호’ 부터 1까지 선형 탐색을 하고 있다

‘비어 있는지를’ 체크하는 좋은 방법이 필요하였고
‘질문’ 탭을 뒤지다가
‘힌트’를 얻었다

• 특정한 비행기 번호 t가 ‘가장 최근까지 탐색한 번호’를
  기억해 두었다가, 그 쪽부터 탐색하기
  

최종 제출 코드

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

int main()
{
	int g, p;
	cin >> g >> p;

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	vector<int> airports(g + 1);
	unordered_map<int, int> checkMap; // 게이트 번호, 가장 마지막에 탐색한 번호

	int answer = 0;

	for (int i = 1; i <= p; i++)
	{
		int t;
		cin >> t;
		bool isSet = false;

		if (checkMap.find(t) == checkMap.end() &&
			airports[t] == 0)
		{
			answer++;
			airports[t] = t;
			checkMap[t] = t;
		}
		else
		{
			int lastFind = checkMap[t];
			if (lastFind == 0)
				lastFind = t - 1;

			for (int j = lastFind - 1; j >= 1; j--)
			{
				if (airports[j] == 0)
				{
					airports[j] = i;
					checkMap[t] = j;
					isSet = true;
					break;
				}
			}

			if (isSet)
				answer++;
			else
				break;
		}

	}

	cout << answer;

	return 0;
}

결과

다행히 통과할 수 있었다

그런데 이 문제는 정석적으로는 유니온-파인드(disjoint set)으로
푸는게 정석이라 하여 추가적인 내용을 작성하였다

유니온 파인드? Disjoint Set?

분리 집합(Disjoint Set)은 ‘서로 겹치지 않는’ 여러 집합의 묶음을 관리하는 자료구조
(Union-Find 라고도 불린다)

• 여러 원소들이 ‘그룹’(집합)으로 나뉘어 있을때,
  
  • 두 원소가 같은 집합에 있는지 빠르게 체크
    
  • 두 집합을 합치는 연산을 효율적으로 처리
    

주요 연산

연산	설명
Find(x)	원소 x가 속한 집합의 대표자(루트)를 찾음.
Union(x,y)	x가 속한 집합과 y가 속한 집합을 합침.
Connected(x,y)	x, y의 대표자가 같은지 비교 → 같은 집합인지 확인.

구현 요소

• 부모 배열(Parent)
  

  처음에는 자기 자신을 부모로 가짐
  

• 경로 압축
  

  Find 수행 시, 지나온 노드들의 부모를 Root로 바로 연결시킴
  

• 랭크/ 크기 기반 합치기(Size/Rank)
  

  작은 트리에 큰 트리를 붙여 트리 높이를 최소화
  

예시 코드

#include <iostream>
#include <vector>
using namespace std;

struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n), size(n,1) {
        for (int i=0; i<n; ++i) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 경로 압축
    }

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a,b);
        parent[b] = a;
        size[a] += size[b]; // 크기 합치기
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

int main() {
    DSU dsu(5); // 0~4
    dsu.unite(0,1);
    dsu.unite(1,2);
    cout << dsu.same(0,2) << "\n"; // 1 (같은 집합)
    cout << dsu.same(3,4) << "\n"; // 0 (다른 집합)
}

활용?

• 그래프
  
  • mst의 Kruskal 알고리즘에서 간선 연결 시, 사이클 여부를 확인
    
  • 네트워크 등의 연결 체크
    
• 이미지 처리 : 픽셀의 그룹화
  
• 게임 : 영역/길 찾기, 길/섬 같은 묶음 관리 방식
  

이번 문제를 해당 알고리즘으로 푼다면?

• 각 게이트 번호를 집합의 대표자(root)로 둔다

• 특정 게이트 x에 비행기 배치시, x와 x-1을 연결시킨다
  (union(x,x-1))
  

• 비행기가 들어올때, find를 통해
  배정이 가능한 게이트를 찾음
  (결과가 0이면 배치가 불가능한 상황이므로 종료)
  

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;

int findSet(int x) {
    if (x == parent[x]) return x;
    return parent[x] = findSet(parent[x]); // 경로 압축
}

void unionSet(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    parent[a] = b; // a 게이트 사용 후 a를 b(=a-1)와 연결
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g, p;
    cin >> g >> p;

    parent.resize(g + 1);
    for (int i = 0; i <= g; i++) parent[i] = i;

    int answer = 0;
    for (int i = 0; i < p; i++) {
        int t;
        cin >> t;

        int gate = findSet(t); // 배정 가능한 최대 게이트
        if (gate == 0) break; // 더 이상 배정 불가

        answer++;
        // gate를 사용했으므로 gate-1로 연결
        unionSet(gate, gate - 1);
    }

    cout << answer << '\n';
    return 0;
}

결론

사실 Union-Find는 이 2 함수가 핵심이다

int findSet(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findSet(parent[x]); // 경로 압축
}

void unionSet(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) parent[a] = b; // a를 b 밑으로 붙임
}

이 2가지 함수를 잘 외워두면
대부분의 Union-Find 문제 해결 가능

• find : 루트를 찾아 나가기
  
• union : 루트를 합치기
  (대표를 찾기, 대표가 다르다면, 대표를 합치기!)
  (합칠때, rank/size 등의 비교 연산 가능)