[c++][프로그래머스] 시험장 나누기

프로그래머스 시험장 나누기 [2021 카카오 채용연계형 인턴십]
https://programmers.co.kr/learn/courses/30/lessons/81305

코딩테스트 연습 - 시험장 나누기

문제 풀이

• 이 문제는 DFS + 파라메트릭 서치(Parametric Search)로 구현했습니다. 
• mid 값을 변화시키면서 다음 시나리오를 따라 그룹을 나누어보면서 mid 값을 최적화합니다. 

위와 같은 트리 형태에서 현재 mid 값이 25 이상이라면 3개의 시험장이 한 그룹으로 묶일 수 있기 때문에 나누지 않습니다. 하지만 mid 값이 18 ~ 24 사이라면 3개의 시험장이 한 그룹으로 묶일 수 없기 때문에 다음과 같이 그룹을 나눠야 합니다. 이는 두 개의 간선 중 하나를 끊어야 한다는 의미입니다. 

우리는 그룹의 최대 인원을 최소화해야하기 때문에 위와 같이 두 개의 경우의 수가 생기게 되면 더 적은 인원의 자식 노드를 선택하여 한 개의 그룹이 되고 더 많은 인원의 자식 노드 쪽을 끊어줍니다. 또, 만약 mid가 17이었다면 9번과 4번 노드는 같은 그룹이 될 경우 18명이 되기 때문에 같은 그룹이 될 수 없어 위와 똑같이 끊어줍니다. 

 

또 다른 시나리오로 위와 같은 상황에서 mid 값이 10~16일 경우가 있습니다. 이 경우에 9번 노드는 7번과 4번 자식 노드 중 누구와도 그룹이 될 수 없기 때문에 아래와 같이 두 개의 간선 모두 끊어줍니다.

또 아래와 같이 자식 노드가 한 개인 경우에도 위와 마찬가지로 그룹으로 묶었을 때 mid 값 보다 작다면 한 그룹으로, mid 값 보다 크다면 간선을 끊어 나누어줍니다. 

DFS를 사용해 리프 노드에서부터 올라가며 현재 그룹에 속한 인원을 리턴하면서 해당 그룹에 내가 속할 수 있는지 or 한 쪽을 끊어야 하는지, 두 쪽 모두 끊어야 하는지를 결정하면 됩니다.

 

코드

#include <vector>

using namespace std;

const int INF = 1e9;
int N, K, mid, cnt;
bool is_pos;

vector<int> tree[10010];
vector<bool> is_root(10010, true);

int dfs(vector<int> &num, int node) {
    if(!is_pos) return INF;
    
    /*
    cnt -> 끊은 간선의 개수, K개의 그룹을 만드려면 간선을 K-1번 끊어야 하는데,
    K번 이상 끊게 되면 잘못된 경우이기 때문에 return
    
    마찬가지로 한 노드의 크기가 mid보다 클 경우 그룹에 속할 수 없기 때문에 return
    */
    if(cnt >= K || num[node] > mid) { 
        is_pos = false;
        return INF;
    }

    if(tree[node].size() == 2) { // 자식 노드 2개인 경우
        int c1 = dfs(num, tree[node][0]);
        int c2 = dfs(num, tree[node][1]);

        // 자식 둘과 한 그룹에 속할 수 있는 경우
        if(c1 + c2 + num[node] <= mid) { 
            return c1 + c2 + num[node];
        }
        
        // 자식 둘과 각각 묶일 수 있는 경우 -> 작은 쪽 선택
        else if(c1 + num[node] <= mid && c2 + num[node] <= mid) {
            cnt++; // 간선 끊는 것 count
            return c1 > c2 ? c2 + num[node] : c1 + num[node];
        }
        else if(c1 + num[node] <= mid) {
            cnt++;
            return c1 + num[node];
        }
        else if(c2 + num[node] <= mid) {
            cnt++;
            return c2 + num[node];
        }
        
        // 자식 둘과 모두 그룹이 될 수 없음
        else {
            cnt += 2; // 양 쪽 간선 모두 끊음
            return num[node];
        }
    }
    else if(tree[node].size() == 1) { // 자식 노드 1개인 경우
        int c = dfs(num, tree[node][0]);

        if(c + num[node] <= mid) return c + num[node];
        else {
            cnt++;
            return num[node];
        }
    }
    else return num[node];
}

bool solve(vector<int> &num, int root) {
    is_pos = true;
    cnt = 0;

    dfs(num, root); 

    if(cnt >= K || !is_pos) return false;

    return true;
}

int solution(int k, vector<int> num, vector<vector<int>> links) {
    int answer = INF;
    N = num.size();
    K = k;

    for(int i=0; i<N; ++i) {
        if(links[i][0] != -1) {
            tree[i].push_back(links[i][0]);
            is_root[links[i][0]] = false;
        }

        if(links[i][1] != -1) {
            tree[i].push_back(links[i][1]);
            is_root[links[i][1]] = false;
        }
    }
    int root = -1;
    for(int i=0; i<N; ++i) {
        if(is_root[i]) {
            root = i;
            break;
        }
    }
    
    int start = 1, end = INF;
    while(start <= end) {
        mid = (start + end) / 2;

        if(solve(num, root)) { 
            /* 
            파라메트릭 서치로 해당 mid 값을 만족하며 그룹을 나눌 수 있을 경우
            우리는 최소값을 원하기 때문에 값을 더 줄여보며 최적화 -> end = mid -1;
            */
            answer = min(answer, mid);
            end = mid - 1;
        }
        else start = mid + 1;
    }

    return answer;
}

실행 결과