[이코테] 탑승구

[ 문제]

 

공항에는 G개의 탑승구가 있으면 각각은 1부터 G까지의 번호로 구분이 된다.

공항에는 P개의 비행기가 차례대로 도킹할 예정이며, i번째 비행기를 1번부터 gi(1<= gi <=G) 탑승구 중 하나에 영구적으로 도킹한다. (이때 다른 비행기는 도킹하지 않은 탑승구에만 도킹할 수 있다.)

또한 P개를 순서대로 도킹하다가 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우 공항의 운행을 중지한다.

비행기를 최대 몇개 도킹할 수 있는지 출력하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에는 탑승구의 갯수 G개. (1 <= G <= 100,000)

둘째줄에는 비행기 수 P개. (1 <= P <= 100,000)

다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi (1 <= gi <= G) 가 주어진다. 이는 i번째 비행기가 1번째부터 gi번째(1<= gi < G) 탑승구 중 하나에 도킹할 수 있다는 의미다. 

 

[출력] 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

 

예시

[입력]

4

3

4

1

1

 

[출력]

2

 

[입력]

4

6

2

2

3

3

4

4

 

[출력]

3

---

그래프 탐색의 조건으로 어떻게 풀어야 할지 일단 고민을 했었다.

일단 각 원소들을 순차탐색을 하면서 서로소 집합을 통해 최대 비행기의 갯수를 구하면 어떨까 생각했었고 이를 표현한 코드는 다음과 같다.

package codingTest;

import java.util.Scanner;

public class BoardingGate {
    public static int findParent(int num, int parent[]) {
        if(parent[num]!= num) {
            parent[num] = findParent(parent[num], parent);
        }

        return parent[num];
    }

    public static void boardingGate(int a, int b, int parent[]) {
        a = findParent(a, parent);
        b = findParent(b, parent);

        if(a<b) {
            parent[b] = a;
        } else if(a>b){
            parent[a] = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int G = sc.nextInt();
        int P = sc.nextInt();
        int flight[] = new int[P];

        for (int i = 0; i < P; i++) {
            flight[i] = sc.nextInt();
        }

        int parent[] = new int[G+1];
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < P; i++) {
            for (int j = i; j < P; j++) {
                boardingGate(flight[i], flight[j], parent);
            }
        }

    }
}

그런데 생각을 다시 해보니까 Scanner를 통해 도킹할 수 있는 탑승구를 P만큼 입력 받는데 이 때 동시에 그래프 탐색을 시작하면 어떨까 생각이 들었다.

아무래도 for 문을 돌아야 하기 때문에 두번 돌리기 번거로울 것 같다는 생각 때문에 그러하였다. 

 

가령 예시 4 3 4 1 1 을 생각해봤을 때, 이렇게 표현이 될 수 있을 것이다.

1번째는 4 탑승구

2번째는 1 탑승구

3번째는 1 탑승구

 

int 배열인 parent는 자기 자신을 각 노드의 부모 노드를 나타내는 그래프로 초기화는 자기 자신으로 초기화가 되어 있다. 

1번 노드는 부모가 1번, 2번 노드는 2번 .... n번 노드는 parent[n] = n 이렇게  되어 있을 것이다. 

각 입력 받은 값들을 parent를 순회하면서 부모 노드를 찾은 뒤에 두 노드가 만약 같다면 종료를 하고, 그렇지 않다면 갯수를 카운트 하는 변수에 계속해서 1을 더해주는 식으로 생각하면 될 거 같다. 

 

이를 토대로 수정한 코드는 다음과 같다.

package codingTest;

import java.util.Scanner;

public class BoardingGate {
    public static int findParent(int num, int parent[]) {
        if(parent[num]!= num) {
            parent[num] = findParent(parent[num], parent);
        }
        return parent[num];
    }

    public static void boardingGate(int a, int b, int parent[]) {
        a = findParent(a, parent);
        b = findParent(b, parent);

        if(a<b) {
            parent[b] = a;
        } else if(a>b){
            parent[a] = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int G = sc.nextInt();
        int P = sc.nextInt();
        int flight[] = new int[P];

        int parent[] = new int[G+1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        int res = 0;

        for (int i = 0; i < P; i++) {
            int find = findParent(sc.nextInt(), parent);
            if(find == 0) {
                break;
            }
            boardingGate(find, find-1, parent);
            res += 1;
        }

        System.out.println(res);
    }
}

 

가령 첫번째 예시를 생각하면 

1번째는 1~4번째 탑승구

2번째는 1~1번째 탑승구

3번째는 1~1번째 탑승구

 

여기서 처음에 find = findParent(4, parent);가 된다. 

여기서 parent는 자기 자신을 초기화 한 것이기에 find 변수 값은 4가 된다.

이 때 boardingGate 함수로 boardGate(4,3,parent)의 합집합 연산이 된다.

여기서 함수 속 들어온 4와 3을 비교하기 때문에 parent[4]의 값이 3이 되고, res 값은 1이 된다.

 

두번째로 find에선 findParent(1, parent)로 find는 1이 된다.

boardingGate(1,0,parent)의 합집합 연산을 통해 parent[1]의 값은 0이 되고, res 값은 2가 된다.

 

3번째 find 에서는 findParent(1,parent)에선 parent[1]의 값과 1의 값이 각각 0과 1로 다르다.

그렇기에 다시 재귀함수 findParent(0, parent)를 호출하여 parent[1]에 넣어주는데 그 값은 0이 된다. 

그런 후 parent[1]의 값을 리턴하여 find에 넣어주는데 그 값은 0이 된다.

0이 되면 break를 통해 for문을 빠져나오게 되고 결과 값은 2가 된다.     

---

두 번째 예시를 통해 생각을 하자면 다음과 같다.

1번째 1~2번째 탑승구

2번째 1~2번째 탑승구

3번째 1~3번째 탑승구

4번째 1~3번째 탑승구

5번째 1~4번째 탑승구

6번째 1~4번째 탑승구

 

입력 2 : findParent(2, parent) -> boardingGate(2,1, parent)를 통해 parent[2] = 1, res = 1이 됨.

입력 2 : findParent(2, parent) -> boardingGate(1,0, parent)를 통해 parent[1] = 0, res = 2가 됨.

입력 3 : findParent(3, parent) -> boardingGate(3,2, parent)를 통해 parent[3] = 1, res = 3이 됨.

입력 4 : findParent(3, parent) -> parent[3]이 1이고 재귀를 통해 parent[1] = 0 이므로 find가 0이 되어서 break를 통해 for문을 빠져나가 결과값은 3이 됨.