문제

춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드1에 숫자를 쌓는 게임을 하려고 합니다.

문제링크

풀이

카드를 떨어뜨리며 카드의 숫자를 정할 수 없다.
모든 카드를 떨어뜨린 뒤 카드의 개수와 target의 크기를 고려하여 카드의 숫자를 정해야 한다.
그래서 카드를 떨어뜨릴 때마다 몇 번째 카드가 어느 노드에 전달되었는지를 저장해두고 나중에 카드의 숫자를 정한 뒤 카드 떨어뜨린 순서에 맞게 answer를 구할 수 있다.

vector<int> result; // 리프노드 방문 순서가 차례대로 들어갈거임

int leafNode = dfs(1, nodes);
result.push_back(v);

카드 떨어뜨리기

카드가 부모 노드를 지나 자식 노드로 이동하면 부모 노드의 간선이 변경된다.
이를 구현하기 위해 queue<int> childNode 자료 구조를 사용하였다.

• 부모 노드의 모든 자식 노드를 오름차순으로 정렬하여 큐에 넣는다.
• 부모 노드에서 자식노드로의 카드 이동은 항상 queue의 맨 앞에 해당하는 노드로 이동한다.
• 카드를 이동시킬 자식노드 번호를 구하고 나면 queue의 맨 앞을 맨 뒤로 이동시켜 자식 노드의 순서를 업데이트한다.

카드 하나를 떨어뜨릴때 위의 과정을 리프노드가 나올때까지 반복한다.
리프노드라면 가지고 있는 카드 수를 +1하고 리프노드를 리턴한다.

int dfs(int v, vector<node>& nodes){
    if (nodes[v].childNode.empty()){ // 리프노드 인 경우
        nodes[v].numberOfCards++;
        return v;
    }
    int n = nodes[v].childNode.front();
    nodes[v].childNode.pop();
    nodes[v].childNode.push(n);

    return dfs(n, nodes);
}

카드 하나의 과정을 정리하였으니 다음은 몇개의 카드를 떨어뜨려야하는지 구해야한다.

카드를 최대한 적게 사용한 경우를 리턴해야 한다.
카드를 한 장씩 떨어뜨리며 매번 모든 리프노드가 가지고 있는 카드로 target의 값을 만들 수 있는지 확인

• 가장 먼저 모든 노드가 target <= 카드의 개수 * 3를 만족하는 경우가 카드를 최대한 적게 사용하여 문제를 해결할 수 있는 경우이다.
• 카드를 하나씩 떨어뜨리다가 노드 중 target < 카드의 개수이 하나라도 발생한다면 해당 입력은 해결할 수 있는 경우가 없으므로 -1을 리턴하도록 한다.

bool flag = true;
while (flag){
    int leafNode = dfs(1, nodes);
    result.push_back(leafNode);

    if (target[leafNode-1] < nodes[leafNode].numberOfCards){
        // 방법이 없는 경우: 
        //아직 카드가 부족한 노드가 있는데, 이미 카드가 넘쳐버린 노드가 있는 경우
        return { -1 };
    }

    //모든 리프노드가 조건을 만족해야 while문이 멈춘다.
    // => 하나라도 만족하지 않으면 while문은 계속 돈다.
    flag = false;
    for (int i =1; i < n; i++){

        if (target[i-1] > nodes[i].numberOfCards * 3){
            flag = true;
        }
    }
}

카드 순서 정하기

문제 해결이 불가능한 경우가 아니라면 각 노드들이 가장 적게 카드를 가지는 경우가 구해진다.
각 노드의 target과 노드가 가지고 있는 카드의 수를 이용하여 각 노드 카드의 숫자값을 결정한다.
문제의 답이 사전순으로 빠른 답을 원하므로 1,2,3 의 우선 순위로 카드의 숫자가 정해졌을 때 남은 카드의 수로 target - 방금 정한 카드 숫자를 만들 수 있는지를 확인한다.

queue<int> getCardSequence(int target, int numberOfCards){
    queue<int> ret;

    while(numberOfCards--){
        for (int number: vector({1,2,3})){
            if (target - number > numberOfCards * 3) continue;
            else if (target - number < numberOfCards) continue;

            ret.push(number);
            target -= number;
            break;
        }
    }

    return ret;
}

모든 리프노드가 getCardSequence()를 통해 카드의 숫자를 정했다면 result에 저장된 노드 순서대로 카드를 앞에서부터 한장씩 꺼내 answer를 작성한다.

for (int i=1; i < n; i++){
    nodes[i].orderOfCards = getCardSequence(target[i-1], nodes[i].numberOfCards);
}

for(int i: result){
    int t = nodes[i].orderOfCards.front();
    nodes[i].orderOfCards.pop();
    answer.push_back(t);
}

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
    int numberOfCards = 0; // 노드가 가지고 있는 카드 개수
    queue<int> childNode; // 자식 노드들이 큐에 순서대로 저장되어 있음
    queue<int> orderOfCards;
};

queue<int> getCardSequence(int target, int numberOfCards){
    queue<int> ret;

    while(numberOfCards--){
        for (int number: vector({1,2,3})){
            if (target - number > numberOfCards * 3) continue;
            else if (target - number < numberOfCards) continue;

            ret.push(number);
            target -= number;
            break;
        }
    }

    return ret;
}

int dfs(int v, vector<node>& nodes){
    if (nodes[v].childNode.empty()){ // 리프노드 인 경우
        nodes[v].numberOfCards++;
        return v;
    }
    int n = nodes[v].childNode.front();
    nodes[v].childNode.pop();
    nodes[v].childNode.push(n);

    return dfs(n, nodes);
}

vector<int> solution(vector<vector<int>> edges, vector<int> target) {
    int n = target.size() + 1;
    vector<int> answer;
    vector<int> result; // 리프노드 방문 순서가 차례대로 들어갈거임
    vector<vector<int>> temp(n);

    vector<node> nodes(n);

    for (vector<int> edge : edges) {
        int par = edge[0];
        int chi = edge[1];

        temp[par].push_back(chi);
    }
    for (int i=0; i < n; i++){
        sort(temp[i].begin(), temp[i].end());
        // childNode[i] <- temp[i];
        for (int j: temp[i]){
            nodes[i].childNode.push(j);
        }
    }

    bool flag = true;
    while (flag){
        int leafNode = dfs(1, nodes);
        result.push_back(v);
        if (target[leafNode-1] < nodes[leafNode].numberOfCards){
            // 방법이 없는 경우: 아직 카드가 부족한 노드가 있는데, 이미 카드가 넘쳐버린 노드가 있는 경우
            return { -1 };
        }

        //모든 리프노드가 조건을 만족해야 while문이 멈춘다. => 하나라도 만족하지 않으면 while문은 계속 돈다.
        flag = false;
        for (int i =1; i < n; i++){

            if (target[i-1] > nodes[i].numberOfCards * 3){
                flag = true;
            }
        }
    }
    

    for (int i=1; i < n; i++){
        nodes[i].orderOfCards = getCardSequence(target[i-1], nodes[i].numberOfCards);
    }

    for(int i: result){
        int t = nodes[i].orderOfCards.front();
        nodes[i].orderOfCards.pop();
        answer.push_back(t);
    }

    return answer;
}