[백준] 10775 공항 c++

문제

www.acmicpc.net/problem/10775

10775번: 공항

 

문제풀이

 

<처음 생각한 풀이>

- 시간 초과

i번째에 g를 입력받는다

 airport배열의 g -> 0 순으로 해당 인덱스가 0이면 그곳에 비행기를 도킹한다고 가정했다.

 

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int airport[100002];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int G, P, g, count = 0;
	bool flag = false;
	cin >> G >> P;
	memset(airport, 0, G + 2);
	for (int i = 0; i < P; i++)
	{
		cin >> g;
		flag = false;
		for (int j = g; j >= 1; j--)
		{
			if (airport[j] == 0) {
				airport[j] = 1;
				flag = true;
				count++;
				break;
			}
		}
		if (!flag)
			break;
	}

	cout << count;


	return 0;
}

 

---

<성공 코드>

 

Union-Find 알고리즘을 사용한다.

 

간단한 Union-Find 코드 (사용하기 전 개념 정리 느낌)

#include <iostream>

using namespace std;

//parent 설정
int getParent(int parent[], int x) {
	if (parent[x] == x)return x;
	return parent[x] = getParent(parent, parent[x]);
}
//각 노드 연결
void UnionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b)parent[b] = a;
	else parent[a] = b;
}
// 연결되어있는 노드인지 확인
int FindParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b)return 1;
	else return 0;
}

int main() {
	int parent[11];
	for (int i = 1; i <= 10; i++)
		parent[i] = i;

	UnionParent(parent, 1, 2);
	UnionParent(parent, 2, 3);
	UnionParent(parent, 3, 4);
	UnionParent(parent, 5, 6);
	UnionParent(parent, 6, 7);
	UnionParent(parent, 7, 8);

	cout << "3과 6은 연결되어 있는가?" << FindParent(parent, 3, 6)<<"\n";
	cout << "6과 8은 연결되어 있는가" << FindParent(parent, 6, 8) << "\n";
	
	return 0;
}

 

하나의 비행기가 Gate [n]에 입력받으면 Union_gate함수를 통해서 Gate[n]의 루트를 Gate[n-1]의 루트로 바꾼다.

(이를 통해서 Gate[n]에 더 이상 비행기를 도킹하지 않는다.)

 

만약 Gate [n]이 0이라면 더 이상 도킹할 수 있는 게이트가 존재하지 않으므로 그 뒤에 입력들은 무시한다.

 

#include <iostream>
#include <vector>

using namespace std;

int get_Rootgate(vector<int>& gate, int a) {
	if (gate[a] == a)return a;
	return gate[a] = get_Rootgate(gate,gate[a]);
}

//a는 main함수 안에서 구했기 때문에 다시 구하지 않는다.
void Union_gate(vector<int>& gate, int a, int b) {
	b = get_Rootgate(gate, b);
	gate[a] = b;
}



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

	int G, P, g,count = 0;
	bool flag = true;
	cin >> G >> P;
	vector<int>plane(P+1);
	vector<int>gate(G + 1);
	for (int i = 0; i <= G; i++)
		gate[i] = i;
	

	for (int i = 0; i < P; i++)
	{
		cin >> plane[i];
		int Rootgate = get_Rootgate(gate, plane[i]);

		if (Rootgate != 0 && flag) {
			Union_gate(gate, Rootgate, Rootgate - 1);
			count++;
		}
		else { //이 후의 입력은 무시한다.
			flag = false;
			continue;
		}
	}

	cout << count;

	return 0;
}

 

참고

<문제 풀이>

jaimemin.tistory.com/772

velog.io/@woga1999/BOJ-10775%EB%B2%88-%EA%B3%B5%ED%95%ADC

 

<Union-Find 개념>

blog.naver.com/ndb796/221230967614