[백준] 알고리즘 분류(그리디 알고리즘,JAVA)10775번, 공항

문제 링크

10775번: 공항

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1~G번까지 게이트가 존재하며, 비행기는 g번 이하의 게이트에 도킹이 가능합니다.

2. 비행기가 도킹에 실패하면 해당 공항은 폐쇄합니다.

3. 비행기를 가장 많이 도킹하는 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. Union-Find를 이용하여 각 비행기의 도킹을 진행합니다.

 

3. Union-Find가 종료된 뒤 도킹한 비행기의 개수를 결과로 출력합니다.

 

 

도킹

 

도킹을 진행할 때 g번 게이트 확인, 도킹이 완료된 게이트일 때 (g-1, g-2, ... 1) 확인합니다.

 

모든 게이트가 도킹이 완료되어있다면 폐쇄!

 

도킹이 되지않은 게이트 존재 시 해당 게이트로 도킹 진행!

 

Union-Find를 통해서 각 게이트들이 도킹되지 않은 게이트로 연결되도록 하였습니다.

 

예를 들어.

 

G = 3, P = 2(3, 3)일 때

 

Union-Find에 사용할 게이트 관련 parent[] 배열

 

※더 이상 도킹이 되지 않는 것을 표현하는 값 : 0

 

 

0	1	2	3
0	1	2	3

g = 3 비행기 도킹 시도

게이트 3번에 도킹 성공! 게이트 3번은 더 이상 도킹이 되지 않고 2(3 -1)번째 게이트에 도킹이 시도됩니다.

0	1	2	3
0	1	2	2

g = 3 비행기 도킹 시도

게이트 3번이 가리키는 도킹 게이트 : 2번 게이트

 

게이트 2번에 도킹 성공! 게이트 2번은 더 이상 도킹이 되지 않고 1(2-1)번째 게이트에 도킹이 시도됩니다.

 

0	1	2	3
0	1	1	1

 

 

예제입력 2.

1. 입력된 정보를 저장합니다.

G : 4

P : 6

 

2 - 2 - 3 - 3 - 4 - 4

2. Union-Find를 이용하여 각 비행기의 도킹을 진행합니다.

 

Union-Find에서 게이트 관련 사용할 parent[] 배열

※더 이상 도킹이 되지 않는 것을 표현하는 값 : 0

 

0	1	2	3	4
0	1	2	3	4

 

g = 2 비행기 도킹 시도

 

게이트 2번에 도킹 성공! 게이트 2번은 더 이상 도킹이 되지 않고 1(2 -1)번째 게이트에 도킹이 시도됩니다.

 

0	1	2	3	4
0	1	1	3	4

 

g = 2 비행기 도킹 시도

게이트 2번이 가리키는 도킹 게이트 : 1번 게이트

 

게이트 1번에 도킹 성공! 게이트 1번은 더 이상 도킹이 되지 않고 0(1 -1)번째 게이트에 도킹이 시도됩니다.

 

0	1	2	3	4
0	0	0	3	4

 

g = 3 비행기 도킹 시도

게이트 3번에 도킹 성공! 게이트 3번은 더 이상 도킹이 되지 않고 2(2 -1)번째 게이트에 도킹을 시도합니다.

 

2번째 게이트가 가리키는 도킹하는 게이트는 0이기 때문에 더 이상 g = 3을 입력받았을 때 도킹이 불가능합니다.

 

0	1	2	3	4
0	0	0	0	4

 

g = 3 비행기 도킹 시도

게이트 3번이 가리키는 도킹 게이트 : 0번 게이트

 

게이트 0번은 도킹을 더 이상 하지 못하는 게이트로써 도킹에 실패하고 공항이 폐쇄합니다.

 

 

3. Union-Find가 종료된 뒤 도킹한 비행기의 개수를 결과로 출력합니다.

 

2 - 2 - 3 - 3 - 4 - 4

 

도킹한 비행기 개수 : 3을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• union, find, parent 함수를 이용해서 비행기 도착하는 순서대로 탐색합니다.
• 대표값이 0일 때는 더 이상 도킹이 불가능한 비행기가 도착한 것으로 공항이 폐쇄됩니다.
• 공항이 폐쇄되거나, 모든 비행기 도킹 이후 도킹한 비행기 개수를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find함수는 Union-Find에서 대표값 찾습니다.
• union함수는 Union-Find에서 두 집합을 합치는 것처럼 대표값을 변경합니다.

import java.io.*;

public class Main{
    static int G, P, answer = 0;
    static int[] parent;	//Union-Find에 게이트 관련 사용할 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        G = Integer.parseInt(br.readLine());
        P = Integer.parseInt(br.readLine());
        parent = new int[G+1];
        //parent[] 배열 초기화
        for(int i=0;i<=G;i++)
            parent[i] = i;
        //각 비행기 Union-Find로 게이트 도킹 시도!
        for(int i=0;i<P;i++){
            int g = Integer.parseInt(br.readLine());
            int pg = find(g);	//도킹할 게이트 구하기
            if(pg==0)	//도킹이 불가능, 공항 폐쇄!
                break;
            union(pg, pg-1);	//도킹 성공 및 다음 도킹할 게이트 설정
            answer++;	//비행기 횟수 증가
        }
        bw.write(answer + "");	//비행기 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //Union-Find에 대표값 찾는 Find 함수
    static int find(int n){
        if(parent[n] == n)
            return n;
        return parent[n] = find(parent[n]);
    }
    //Union-Find에 두 집합 대표값 같게 만드는 Union 함수
    static void union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        //b의 값에 g-1값이 들어가기 때문에 parent[pa]값을 변경합니다.
        if(pa != pb)
            parent[pa] = pb;
    }
}