춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드1에 숫자를 쌓는 게임을 하려고 합니다. 아래 그림은 게임의 예시를 나타냅니다.
트리의 모든 간선은 부모 노드가 자식 노드를 가리키는 단방향 간선입니다.
모든 부모 노드는 자식 노드와 연결된 간선 중 하나를 길로 설정합니다.
실선 화살표는 길인 간선입니다.
점선 화살표는 길이 아닌 간선입니다.
모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다.
[게임의 규칙]은 아래와 같습니다.
1번 노드(루트 노드)에 숫자 1, 2, 3 중 하나를 떨어트립니다.
숫자는 길인 간선을 따라 리프 노드까지 떨어집니다.
숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.
만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드를 가리키는 간선을 길로 설정합니다.
노드의 간선이 하나라면 계속 하나의 간선을 길로 설정합니다.
원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있습니다.
단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 합니다.
* 문제 예시는 위 링크를 참조해 주세요!
트리의 각 노드들의 연결 관계를 담은 2차원 정수 배열 edges, 각 노드별로 만들어야 하는 숫자의 합을 담은 1차원 정수 배열 target이 매개변수로 주어집니다. 이때, target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우를 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. 만약, target대로 숫자의 합을 만들 수 없는 경우 [-1]을 return 해주세요.
우선, 트리의 노드 개수는 기껏해야 100이므로, 최대 리프 노드 개수는 99개이다. 경우의 수가 매우 작으므로, 브루트 포스로도 도달하는 리프 노드의 순서와 가능 여부를 충분히 제한 리소스로도 테스트해 볼 수 있다.
이 문제의 쟁점은 다음과 같아진다.
1. 문제에서 요구하는 대로 가리키는 자식 노드를 지정하는 트리 구조를 구현하는 것이 선결 문제이다. 각 노드에 대해 현재 가리키는 자식 노드의 인덱스와 자식 노드의 리스트가 저장되어야 한다. 탐색을 통해 이러한 정보들을 저장하는 트리를 구성하고, 1회 진행시마다 현재 가리키는 최종 리프노드와 각 노드들의 인덱스 정보 변화를 처리할 수 있어야 한다.
2. 이 때, 각 리프 노드 i의 방문 순서와 방문 횟수를 저장하자. 숫자는 1,2,3이 가능하므로 (방문 횟수) ~ (3*방문 횟수) 만큼의 범위를 나타낼 수 있다. 목표값 target[i]이 이 범위에 들어가게 된다면 이 노드는 목표값을 나타낼 수 있다는 의미가 되므로 이 노드는 조건을 만족한다.
만약 모든 노드가 이 조건을 만족하지 않았음에도, 어떤 노드의 방문 횟수 범위가 목표값을 벗어나는 경우를 생각해보자. 이 경우는 target[i] 보다 방문 횟수가 더 커졌음을 의미한다. 이 경우 노드는 어떤 경우라도 target[i]를 만들 수 없으므로 [-1]를 반환해야 한다.
모든 노드가 이 조건을 만족하는 순간이 result의 조건 중 하나인 가장 짧은 정답을 만족하게 되므로, 더 이상의 탐색을 중지하고 3으로 넘어간다.
3. 사전순으로 가장 앞선 해답이 되려면, 모든 리프 노드 i에 대해 가급적 많은 1을 사용하고 또한 1-2-3 순으로 순서 배치가 일어나야 한다. 2에서 우리는 각 리프 노드의 방문 횟수를 알게 되었으므로, 주어진 방문 횟수 중 목표값 target[i]이 되도록 1, 2, 3의 개수를 정해야 한다. 이 때, 과잉 방문횟수를 현재 방문횟수와 필요한 최소방문횟수(target[i])로 가정하자. 그렇다면 3의 개수는 과잉방문횟수를 2로 나눈 몫, 2의 개수는 그 나머지, 1의 개수는 전체 횟수에서 3의 개수와 2의 개수를 뺀 값이 된다. 다음 예시를 보면 이해가 빨라진다.
총 5개의 1, 2, 3을 사용하여 11을 나타내는 방법 중, 사전적으로 가장 앞서는 경우를 구한다고 가정하자.
여기서 과잉 방문횟수는 11 - 5 = 6이 된다.
5개의 1, 2, 3을 사용해야 한다는 뜻은, 필수적으로 총합 5가 소요되며, 남은 5개의 숫자를 [0, 1, 2]중에서 고르는 경우와 같다.
따라서 위 문제는 총 5개의 0, 1, 2를 사용하여 과잉 방문횟수 6을 나타내는 방법을 찾는 문제로 변환된다.
이 때, 2의 개수, 그리고 1의 개수의 우선순위 순으로 최대한 많이 사용해야 사전적으로 가장 앞서는 경우를 구할 수 있다. 이 때 2의 개수의 최댓값은 6 // 2 = 3이 된다. 그리고 1의 개수는 6 % 2 = 0. 즉 불필요하다.
이를 다시 앞선 문제로 치환하면, 문제에서 요구하는 답은 (2+1)을 3개, 그리고 (0+1)를 나머지 2개 사용하여 사전순으로 정렬한 [1, 1, 3, 3, 3] 이 된다.
이러한 방식을 일반화한다면 위와 같은 결과가 나온다.
이렇게 완성된 각 리프 노드의 사전 리스트를 등장 순서대로 배열하면 전체 정답이 완성된다.
다시 만난 카카오 코테 마지막 문제는 생각보단 어렵지 않았다. 그 때는 주기성을 생각해 공식을 찾으려다 남은 시간을 다 빼앗겼었는데, 좀 더 쉽게 생각하니 더 쉽게 풀렸다. 그때는 코테 막바지 시간대기도 해서 마음에 여유가 없었고, 이런 발상의 전환이 쉽지 않았던 것 같다. 역시 실전은 이런 연습과는 차원이 다른거같다 ㅠㅠ....
풀이 코드
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)
def solution(edges, target):
edge_dict = defaultdict(list)
tree_dict = defaultdict(list)
visited = [False]*len(target)
visited[0] = True
for a, b in edges :
edge_dict[a-1].append(b-1)
edge_dict[b-1].append(a-1)
def dfs(node) :
child_list = list()
for child in edge_dict[node] :
if visited[child] :
continue
visited[child] = True
child_list.append(child)
if not child_list :
return [node]
tree_dict[node].extend([0, sorted(child_list)])
leaf_list = list()
for child in child_list :
leaf_list.extend(dfs(child))
return leaf_list
def search(node) :
if len(tree_dict[node]) == 0 :
return node
idx = tree_dict[node][0]
tree_dict[node][0] = (tree_dict[node][0] + 1) % len(tree_dict[node][1])
return search(tree_dict[node][1][idx])
leaf_list = dfs(0)
leaf_cap_dict = { key : 0 for key in leaf_list }
is_leaf_succeeded = { key : False if target[key] > 0 else True for key in leaf_list }
order_list = list()
while False in is_leaf_succeeded.values() :
cur_node = search(0)
leaf_cap_dict[cur_node] += 1
if leaf_cap_dict[cur_node] > target[cur_node] :
return [-1]
if not is_leaf_succeeded[cur_node] and leaf_cap_dict[cur_node]*3 >= target[cur_node] :
is_leaf_succeeded[cur_node] = True
order_list.append(cur_node)
answer = [0]*len(order_list)
for leaf in leaf_list :
leaf_result = list()
sur_cap = target[leaf] - leaf_cap_dict[leaf]
leaf_result = [1]*(leaf_cap_dict[leaf] - sur_cap % 2 - sur_cap // 2) + [2]*(sur_cap % 2) + [3]*(sur_cap // 2)
for idx, node in enumerate(order_list) :
if node == leaf :
answer[idx] = leaf_result.pop(0)
return answer
