[프로그래머스/JAVA] 81305번 시험장 나누기 (DFS, 이진탐색)

문제

문제 링크

시험장 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/81305

프로그래머스

 

문제 설명

카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다.

예제 예시 이미지

 

• 하나의 노드는 하나의 시험장을 나타냅니다.
• 검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다.
  • 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다.
• 노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.
  • 위의 그림에서, 9번 시험장에는 10명, 4번 시험장에는 8명, 6번 시험장에는 20명의 응시자가 시험을 볼 예정입니다.
• 노드 사이의 간선은 해당 시험장이 연결되어 있음을 의미합니다.
  • 위의 그림에서, 9번 시험장은 7번 시험장과, 7번 시험장은 6번 시험장과 연결되어 있습니다.

 

코딩 테스트를 총괄하는 무지는 안정적인 시험을 위해, 시험장에서 오는 트래픽을 k개의 그룹으로 나누어 각 그룹별 서버로 분산시키기로 하였습니다.

시험장 사이를 연결한 간선들 중 k-1개를 끊어서 시험장을 k 개의 그룹으로 나눌 계획입니다.

이때, 그룹별 최대 트래픽을 최소화하기 위하여 가장 큰 그룹의 인원을 최소화시켜야 합니다.

 

나눌 그룹의 수를 나타내는 정수 k, 각 시험장의 응시자 수를 나타내는 1차원 정수 배열 num, 시험장의 연결 상태를 나타내는 2차원 정수 배열 links가 매개변수로 주어집니다.

인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return 하도록 solution 함수를 완성해주세요.

  

 

제한 사항

• 1 ≤ k ≤ 10,000
• k ≤ num의 길이 ≤ 10,000
  • num[i]에는 i번 시험장의 응시자 수가 담겨있습니다.
  • 1 ≤ num의 원소 ≤ 10,000
• links의 길이 = num의 길이
  • links의 i번째 행은 i번 노드(시험장)의 [왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호]입니다.
    • 해당 위치에 자식 노드가 없는 경우 -1이 담겨있습니다.
    • 잘못된 노드 번호나, 하나의 이진 트리 구조가 아닌 입력은 주어지지 않습니다.

 

입출력 예시

입출력 예시

 

 

문제 풀이

 

접근 방법

• 연결된 간선 k-1 개를 모든 조합으로 나눠서 그룹의 수를 계산하기엔 너무 복잡도가 높아서 완전 탐색보단 이진 탐색으로 생각해보자.
• 특정 x 명인 그룹이 최대로 k 개의 그룹이 나누어 지는지, 이 중의 k개 그룹으로 나눠지는 x의 최대 x 는 무엇일까
  
  • 그룹의 인원의 범위는 최소 모든 노드를 나눈 '노드의 최댓값' 에서 모든 시험장이 한 그룹인 '노드들의 총합' 까지 이다.
  • 즉, 범위는 num.max ≤ x ≤ num.sum 이다.
• 탐색은 DFS 로 하면서 그룹을 나누는 기준이 필요하다. 기준은 총 3개가 필요하다.
  • 노드를 탐색하면서 현재 노드의 값(node), 왼쪽 자식들의 합(left), 오른쪽 자식들의 합(right)을 계산한다.
  • 1. 그룹을 나누지 않는다. (node + left + right ≤ x)
    • node + left + right 의 합이 x 보다 작으면 그룹을 나눌 필요가 없다.
  • 2. 두 그룹으로 나눈다. (1 cut)
    • 1에 해당되지 않은 (x ≤ node + left + right) 노드 중에 node+left or node+right 둘 중 하나가 x 를 넘지 않으면 1번 나눈다.
  • 3. 세 그룹으로 나눈다. (2 cut)
    • 1,2 에 해당하지 않은 경우 2번 나눈다.

 

코드

public class P_81305 {

    // 몇번 그룹을 나눌지 저장하는 전역변수
    static int cut = 0;

    // 루트 노드(시험장) 번호저장
    static int root;

    // 연결 노드
    static int[][] trees;

    // 노드(시험장)의 학생수
    static int[] amount;

    private static int solution(int k, int[] num, int[][] links) {

        // 특정 x 명인 그룹이 최대로 k 개의 그룹이 나누어 지는지, 이 중의 k개 그룹으로 나눠지는 x의 최소 x 는 무엇인가?
        // x 의 범위는 num.max ≤ x ≤ num.sum

        int start = 0;
        int end = 0;

        int limit;

        trees = links;
        amount = num;

        // 루트 노드 찾기
        findRoot(num.length);

        // 이진 탐색 범위
        // start : 노드의 최댓값
        // end : 노드들의 합
        for (int n : num) {
            start = Math.max(n, start);
            end += n;
        }

        // 이진 탐색 시작
        while (start<end) {
            limit = (start + end)/2;

            if (getGroup(limit) <= k) {
                end = limit;
            } else {
                start = limit+1;
            }
        }

        return start;
    }


    // root 노드 찾는 함수
    private static void findRoot(int size) {
        boolean[] notRoot = new boolean[size];

        // root 를 찾기
        // 자식이 없으면 root
        for (int[] tree : trees) {
            if (tree[0] != -1) notRoot[tree[0]] = true;
            if (tree[1] != -1) notRoot[tree[1]] = true;
        }

        for (int i=0; i<notRoot.length; i++) {
            if(!notRoot[i]) {
                root = i;
                break;
            }
        }
    }

    // 개별 그룹의 최대 학생수 limit 을 안넘는 그룹 개수
    private static int getGroup(int limit) {
        cut = 0;
        DFS(root, limit);

        // 총 그룹수는 나눈 횟수 + 1
        return cut+1;
    }


    // 시험잠 탐색
    private static int DFS(int node, int limit) {

        int left, right;

        left = (trees[node][0] == -1) ? 0 : DFS(trees[node][0], limit);
        right = (trees[node][1] == -1) ? 0 : DFS(trees[node][1], limit);

        // 1. 그룹이 나뉘어지지 않는다.(N + L + R ≤ limit)
        if(amount[node] + left + right <= limit) {
            return amount[node] + left + right;
        }
        

        // 2. 2그룹으로 나눈다. 
        // 2그룹으로 나눌수 있는 조건이 한번은 cut 나야하니까 (N + L + R ≥ limit 이기 때문에)
        // node + min ≤ limit 값이면 1번만 cut. 이외면 2번 cut.
        if (amount[node] + Math.min(left, right) <= limit) {
            cut+=1;
            return amount[node] + Math.min(left,right);
        }

        // 3. 이외에는 3그룹으로 나눈다.
        cut += 2;
        return amount[node];
    }
}