이코테 - 탑승구 with JAVA

 

 

해당 문제가 다른 문제들과 다른 점은 union연산에서 부모를 던진다는 점이다.

 

왜 부모를 던지는 것일까?

해당 문제의 로직을 살펴보면 만약 1~4 탑승구 중 하나에 착륙이 가능한 비행기가 들어온다면 탑승구 4와 탑승구 3를 union 한다.

이렇게 반복을 하다 부모의 값이 0이라면 착륙이 불가능하게 처리한다.

 

0을 만들기 위해서는 부모를 던져야 한다.

예를 들어, 2, 2 비행기가 들어왔다고 가정하자

초기 부모는 다음과 같다 [0, 1, 2, 3]

2 비행기 착륙 : 0, 1, 1, 3

2 비행기 착륙 : 0, 0, 1, 3

과 같이 된다. (부모를 던졌다는 가정하에)

따라서, 이 후, 추가적으로 2이하의 수가 들어오면 0을 반환하고 종료된다.

 

 

 

 

코드

package JAVA.TCT.GraphTheory;

import java.util.*;

public class Q2 {
    public static int[] parent;
    public static void main(String[] args){

        // 기본 입력 및 설정
        Scanner sc = new Scanner(System.in);
        int g = sc.nextInt();
        int p = sc.nextInt();
        parent = new int[g+1];
        for(int i=0; i<=g; i++){
            parent[i] = i;
        }
        List<Integer> planes = new ArrayList<>();
        for(int i=0; i<p; i++){
            planes.add(sc.nextInt());
        }

        // 로직
        int result = 0;
        for(int plane1 : planes){
            int parent1 = find_parent(plane1);
            if(parent1 == 0){
                break;
            }
            result += 1;
            union_parent(parent1, parent1-1);
            for(int i : parent){
                System.out.print(i);
            }
            System.out.println(" ");
        }
        System.out.println(result);
    }
    public static int find_parent(int node){
        if(parent[node] != node){
            parent[node] = find_parent(parent[node]);
        }
        return parent[node];
    }
    public static void union_parent(int node1, int node2){
        int parent1 = find_parent(node1);
        int parent2 = find_parent(node2);
        parent[parent1] = (parent1 > parent2) ? parent2 : parent1;
        parent[parent2] = (parent1 > parent2) ? parent2 : parent1;
    }
}