백준 10775 - 공항

Java

10775 번 - 공항

문제

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

접근 방법

코드

import java.util.*;
import java.io.*;

public class Main {
	static int G,P, result;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	G = stoi(br.readLine());
    	P = stoi(br.readLine());
    	
    	parent = new int[G + 1];
    	
    	int curG;
    	init();
    	for(int i = 0; i < P; i++) {
    		curG = stoi(br.readLine());
			// 만약 넣으려는 게이트가 이미 꽉차있으면
    		if(findSet(curG) == 0)
    			break;
			// 현재 게이트와 이전 게이트와 유니온
    		union(curG, findSet(curG) - 1);
    		result++;
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	// --------- Disjoint Set 시작 ------------
	static void init() {
		for(int i = 1; i <= G; i++) {
			parent[i] = i;
		}
	}
	
	static int findSet(int num) {
		if(parent[num] == num)
			return num;
		return parent[num] = findSet(parent[num]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot)
			return false;
		int min = Math.min(aRoot, bRoot);
		parent[aRoot] = min;
		parent[bRoot] = min;
		return true;
	}
	// --------- Disjoint Set 끝 ------------
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점

없습니다.