백준 10775번 : 공항 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

공항 골드 2

 

📖 문제

 

서로소 집합의 경로 압축 방법을 사용하여 풀었다.

 

각 게이트는 도킹 가능한 게이트를 가리킨다. 처음에는 각자 자신을 가리키지만 

비행기 도킹시 각 게이트는 자신의 게이트는 이미 도킹되었으므로 도킹 가능한 게이트를 가리켜준다. 

만약 가리킨 게이트가 0이라면 이는 더이상 도킹할 수 없다는 의미이다. 

 

예제 2번을 예시로 들어보면

2 2 3 3 4 4 비행기 순서 

1 2 3 4 게이트    
1 2 3 4 게이트가 가리키는 도킹 가능 게이트 

1) 1번째 비행기 도킹
1 2 3 4    2번째에 도킹후 2번 게이트는 방문처리후 -1로 이전 게이트를 가리키게 한다. 
1 1 3 4    

2) 2번째 비행기 도킹

1 2 3 4    2번째 도킹 시도시 이미 방문을 했기에 가리키는 게이트로 이동한다. 여기서는 1번 게이트 
0 0 3 4    1번 게이트 방문처리후 -1로 이전 게이트를 가리킨다. 
           1번게이트까지 왔던 경로대로 돌아가서 가리키는 게이트를 갱신한다. 


3) 3번째 비행기 도킹
1 2 3 4  // 3번째 도킹 후 방문처리 및 -1로 이전 게이트를 가리키게 한다. 
0 0 2 4 

4) 4번째 비행기 도킹
 1  2  3  4  // 4번째 도킹 시도시 이미 방문했기에 가리키는 2번 게이트로 이동, 2번 게이트도 방문했기에
-1 -1 -1  4 // 0번 게이트로 이동, 0번게이트는 더이상 이동 불가이기에 -1로 갱신 후 반환

---

🔅 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static boolean[] visited; // 각 게이트가 이미 사용되었는지 여부
    static int[] targetedGates; // 각 게이트가 연결된 다음 게이트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int G = Integer.parseInt(br.readLine());
        int P = Integer.parseInt(br.readLine());

        visited = new boolean[G + 1];
        targetedGates = IntStream.range(0, G + 1).toArray();
        
        int cnt = 0; // 도킹 가능 비행기 수 

        for (int i = 0; i < P; i++) {
            int g = Integer.parseInt(br.readLine());

            int result = dfs(g); // 도킹 가능한 게이트 탐색
            if (result == -1) break; // 도킹 불가시 종료
            else cnt++; // 도킹 성공시 카운트 + 1
        }

        System.out.println(cnt);
    }


    // 유니온 파인드 기반 재귀 탐색
    // 해당 게이트 이하에서 도킹 가능한 게이트를 찾아서 반환
    private static int dfs(int gate) {
        // 현재 비행기가 가고싶은 게이트가 가리키는 게이트가 0번째 게이트 즉, 갈 수 있는 게이트가 없다면 -1 반환
        if (targetedGates[gate] == 0) return -1;

        // 방문 하지 않았으면 방문 처리후 목표게이트는 이전 게이트를 가리키도록 갱신
        if (!visited[gate]) {
            visited[gate] = true;
            targetedGates[gate]--;
            return targetedGates[gate];
        }

        // 경로 압축
        // 방문했다면 현재 게이트가 가리키는 다음 게이트로 재귀 탐색
        return targetedGates[gate] = dfs(targetedGates[gate]);
    }


}

 

 

 

❗ 오답노트 / 필요한 지식

1.