[알고리즘][X][RE] 1,2,3 떨어트리기

문제 설명
춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드1에 숫자를 쌓는 게임을 하려고 합니다.
아래 그림은 게임의 예시를 나타냅니다.

railroad.jpg

트리의 모든 간선은 부모 노드가 자식 노드를 가리키는 단방향 간선입니다.
모든 부모 노드는 자식 노드와 연결된 간선 중 하나를 길로 설정합니다.
실선 화살표는 길인 간선입니다.
점선 화살표는 길이 아닌 간선입니다.
모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다.
[게임의 규칙]은 아래와 같습니다.

1번 노드(루트 노드)에 숫자 1, 2, 3 중 하나를 떨어트립니다.
숫자는 길인 간선을 따라 리프 노드까지 떨어집니다.
숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.
만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드를 가리키는 간선을 길로 설정합니다.
노드의 간선이 하나라면 계속 하나의 간선을 길로 설정합니다.
원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있습니다.
단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 합니다.
[게임의 목표]는 각각의 리프 노드에 쌓인 숫자의 합을 target에서 가리키는 값과 같게 만드는 것입니다.
예를 들어, target이 [0, 0, 0, 3, 0, 0, 5, 1, 2, 3]일 경우 아래 표와 같은 의미를 가집니다.

노드 번호	노드에 쌓인 숫자의 합
1	0
2	0
3	0
4	3
5	0
6	0
7	5
8	1
9	2
10	3
target대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해서는 [2, 1, 2, 2, 1, 3, 3]순으로 숫자를 떨어트리면 됩니다.

아래 두 그림은 순서대로 1, 2번째 숫자 [2, 1]을 떨어트린 뒤의 길 상황을 나타냅니다.
railroad21.jpg

숫자 2는 떨어지면서 1번 노드와 2번 노드를 지나갔습니다.
1번 노드는 3번 노드를 가리키는 간선을 길로 설정합니다.
2번 노드는 5번 노드를 가리키는 간선을 길로 설정합니다.
숫자 1은 떨어지면서 1번 노드, 3번 노드, 6번 노드를 지나갔습니다.
1번 노드는 3번 노드보다 번호가 큰 노드를 가리키는 간선이 없으므로 다시 2번 노드를 가리키는 간선을 길로 설정합니다.
3번 노드는 간선이 하나이므로 계속해서 6번 노드를 가리키는 간선을 길로 설정합니다.
6번 노드는 9번 노드를 가리키는 간선을 길로 설정합니다.
아래 두 그림은 순서대로 3, 4번째 숫자 [2, 2]를 떨어트린 뒤의 길 상황을 나타냅니다.
railroad2122.jpg

아래 세 그림은 순서대로 5, 6, 7번째 숫자 [1, 3, 3]을 떨어트린 뒤의 길 상황을 나타냅니다.
railroad2122133.jpg

각 리프 노드에 쌓인 숫자를 모두 더해 배열로 나타내면 target과 같습니다.

트리의 각 노드들의 연결 관계를 담은 2차원 정수 배열 edges, 각 노드별로 만들어야 하는 숫자의 합을 담은 1차원 정수 배열 target이 매개변수로 주어집니다. 이때, target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우를 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. 만약, target대로 숫자의 합을 만들 수 없는 경우 [-1]을 return 해주세요.

제한사항
1 ≤ edges의 길이 ≤ 100
edges[i]는 [부모 노드 번호, 자식 노드 번호] 형태로, 단방향으로 연결된 두 노드를 나타냅니다.
1 ≤ 노드 번호 ≤ edges의 길이 + 1
동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
항상 하나의 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
1번 노드는 항상 루트 노드입니다.
target의 길이 = edges의 길이 + 1
target[i]는 i + 1번 노드에 쌓인 숫자의 합으로 만들어야 하는 수를 나타냅니다.
0 ≤ 리프 노드의 target값 ≤ 100
리프 노드를 제외한 노드의 target값 = 0
target의 원소의 합은 1 이상입니다.
입출력 예
edges	target	result
[[2, 4], [1, 2], [6, 8], [1, 3], [5, 7], [2, 5], [3, 6], [6, 10], [6, 9]]	[0, 0, 0, 3, 0, 0, 5, 1, 2, 3]	[1, 1, 2, 2, 2, 3, 3]
[[1, 2], [1, 3]]	[0, 7, 3]	[1, 1, 3, 2, 3]
[[1, 3], [1, 2]]	[0, 7, 1]	[-1]
입출력 예 설명
입출력 예 #1

문제 예시와 같습니다. 위의 설명처럼 [2, 1, 2, 2, 1, 3, 3]순으로 숫자를 떨어트리면 target과 같게 만들 수 있지만, 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우는 [1, 1, 2, 2, 2, 3, 3]입니다.

입출력 예 #2

[3, 2, 1, 1, 3]순으로 숫자를 떨어트리거나 [1, 1, 1, 1, 2, 1, 3]순으로 숫자를 떨어트려도 target과 같게 만들 수 있지만, 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우는 [1, 1, 3, 2, 3]입니다.

railroad ex2.jpg

입출력 예 #3

예제 3번의 트리는 주어지는 edges의 순서만 다를 뿐, 예제 2번과 같은 트리입니다. 2번 노드에 쌓인 숫자의 합을 7로 만들면서 3번 노드에 쌓인 숫자의 합을 1로 만들도록 숫자를 떨어트리는 방법은 없습니다.
따라서 [-1]을 return 해야 합니다.

리프 노드는 자식 노드가 없는 노드를 뜻합니다. ↩

틀린 풀이

- tree 구조여서 tree class를 직접 만들어서 해결하고자 했으나 여러 예기치 못한 에러가 터져서 일단 숨을 고르고 다음에 다시 봐야겠다.

class Node:
    
    def __init__(self, number, value, cur_idx=0):
        self.number = number
        self.value = value
        self.child_nodes = []
        self.cur_idx = cur_idx

class Tree:
    
    def __init__(self):
        self.root_node = Node(1, None)
        self.n = 0
        
    def __len__(self):
        return self.n
        
    def make_node(self, number, value, cur_idx=0):
        new_node = Node(number, value, cur_idx)
        self.n += 1
        return new_node
    
    def find_node(self, cur_node, target):
        if target == cur_node.number:
            return cur_node
        
        for child_node in cur_node.child_nodes:
            result = self.find_node(child_node, target)
            if result:
                return result
        
        return None
            
    def make_child(self, number, child_number):
        child_node = self.find_node(self.root_node, child_number)
        if not child_node:
            child_node = self.make_node(child_number, 0)
            
        parent_node = self.find_node(self.root_node, number)
        if not parent_node:
            parent_node = self.make_node(number, 0, 0)
        parent_node.child_nodes.append(child_node)
        parent_node.child_nodes.sort(key=lambda x: x.number)
    
    def change_direction(self, cur_node=None):
        if cur_node is None:
            cur_node = self.root_node
        if not cur_node.child_nodes:
            return
        
        cur_node.cur_idx = (cur_node.cur_idx + 1) % len(cur_node.child_nodes)
        for child_node in cur_node.child_nodes:
            self.change_direction(child_node)
    
    def shoot_value(self, value):
        cur_node = self.root_node
        
        while cur_node.child_nodes:
            next_node = cur_node.child_nodes[cur_node.cur_idx]
            cur_node = next_node
        
        cur_node.value += value
        
        self.change_direction()
        
            
    def __str__(self, cur_node=None):
        if cur_node is None:
            cur_node = self.root_node
        print(cur_node.number)
        print("--")
        for child_node in cur_node.child_nodes:
            self.__str__(child_node)
        
        return "FINISH"
    
    def make_answer(self):
        for i in range(1, self.n+1):
            num_i_node = self.find_node(self.root_node, i)
            print(num_i_node.number, num_i_node.value, num_i_node.child_nodes, num_i_node.cur_idx)
            

def solution(edges, target):
    # 최소를 찾는 것이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 방법이 없으므로 그리디 X
    # 중간 결과를 이용할 방법이 없으므로 DP X
    # 따라서 탐색
    # 먼저 트리 구조를 만들어야 한다.
    # 각각의 노드는 다음을 가진다. 자신의 번호, 자식 번호, 값
    # 자식이 없으면 리프 노드이다.
    
    trees = Tree()
    for edge in edges:
        parent_number, child_number = edge
        trees.make_child(parent_number, child_number)
    
    # for i in range(5):
    #     trees.shoot_value(1)
    
    trees.make_answer()
    
    answer = []
    return answer

solution([[2, 4], [1, 2], [6, 8], [1, 3], [5, 7], [2, 5], [3, 6], [6, 10], [6, 9]]	,[0, 0, 0, 3, 0, 0, 5, 1, 2, 3]	)

- 다른 사람의 풀이를 참고해보니 tree로 해결할 수도 있다.

- 다음에 확인해보자!!

 

Reference

---

https://school.programmers.co.kr/learn/courses/30/lessons/150364/solution_groups?language=python3