백준 10775 - 공항

백준 10775 - 공항

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

★ 풀이

그리디 : 항상 가능한 끝 게이트 먼저 채워야지 최대한 많은 수의 비행기를 도킹할 수 있다.

분리집합 : 그리디하게 채울 노드(게이트) 번호를 찾은 다음 채울 노드와 예비 노드를 병합한다.

find를 이용해서 채울 게이트를 탐색했을 때 더이상 채울 게이트가 존재하지 않는다면(0을 가리킴)

그 이후부턴 공항 폐쇄..

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int g,p; static int airplane[],parent[],rank[]; public static void main(String[] args) throws IOException { g = Integer.parseInt(br.readLine()); p = Integer.parseInt(br.readLine()); rank = new int[g+1]; parent = new int[g+1]; for(int i = 1; i<=g; i++) { parent[i] = i; } airplane = new int[p+1]; for(int i = 1; i<=p; i++) { airplane[i] = Integer.parseInt(br.readLine()); } int ans = 0; for(int i = 1; i<=p; i++) { int emptyGate = find(airplane[i]); if(emptyGate == 0) break; ans++; union(emptyGate, emptyGate - 1); // 현재와 예비 } System.out.println(ans); } static int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } static void union(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(rank[a] > rank[b]) { int tmp = a; a = b; b = tmp; } parent[a] = b; if(rank[a] == rank[b]) rank[a]++; } }

from http://sweet-smell.tistory.com/143 by ccl(A) rewrite - 2021-12-07 20:27:03