프로그래머스

프로그래머스 리프 노드 수 최대화 풀이: DFS와 그리디

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

루트 노드에서 시작하는 트리를 만들 때 리프 노드의 수를 최대로 만드는 문제입니다. 루트는 자식 하나를 가지며, 나머지 노드는 자식 2개, 자식 3개 또는 자식 0개를 가질 수 있습니다.

자식이 0개인 노드가 리프 노드이고, 자식이 2개 또는 3개인 노드가 분배 노드입니다. 분배 노드는 최대 dist_limit개까지 사용할 수 있습니다.

같은 깊이에 있는 분배 노드는 모두 같은 수의 자식을 가져야 하며, 리프의 분배도는 경로에 있는 자식 수의 곱입니다. 모든 리프의 분배도가 split_limit 이하가 되도록 하면서 만들 수 있는 리프 수의 최댓값을 구합니다.

dist_limit와 split_limit은 최대 10억이므로 노드를 직접 만들 수 없습니다. 대신 깊이별로 분배 노드가 2개 또는 3개의 자식을 가지는 선택만 탐색해야 합니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

트리를 깊이별 분기 수로 압축하기

같은 깊이의 분배 노드는 모두 같은 자식 수를 가져야 합니다. 따라서 실제 노드 연결을 만들지 않고 다음과 같은 분기 순서만 결정하면 됩니다.

깊이 1: 2 또는 3
깊이 2: 2 또는 3
깊이 3: 2 또는 3
...

DFS 상태는 다음 네 값으로 표현합니다.

  • cur: 현재 깊이에서 확장할 수 있는 노드 수
  • used: 지금까지 분배 노드로 사용한 수
  • split: 현재까지의 분배도 곱
  • leaf: 이미 리프로 확정된 노드 수

현재 상태에서 더 확장하지 않으면 cur에 있는 노드도 모두 리프가 되므로 현재 리프 수는 leaf + cur입니다.

분배도 제한으로 깊이 제한하기

분배 노드의 자식 수를 선택하면 split은 2 또는 3배가 됩니다. 따라서 split_limit이 10억이어도 가능한 깊이는 많지 않습니다.

next_split = split * child
if next_split > split_limit:
    continue

이 조건을 통과하지 못하는 가지는 더 깊게 내려갈 수 없으므로 가지치기합니다.

다음 단계에 분배 노드를 최대한 넘기는 그리디

현재 깊이에서 새로 생긴 next_nodes 중 일부는 분배 노드로 확장하고 나머지는 리프로 확정할 수 있습니다. 다음 깊이로 넘길 수 있는 분배 노드 수는 남은 한도 안에서 최대한 많이 선택하는 것이 유리합니다.

분배 노드는 이후에 자식 2개 또는 3개를 만들어 리프 수를 늘릴 수 있지만, 리프로 확정하면 더 이상 확장할 수 없기 때문입니다. 따라서 다음 단계로 넘길 수는 수를 next_cur = min(next_nodes, remain)으로 고정하고, 넘기지 못한 노드는 즉시 리프로 계산합니다.

복잡도

분기 선택은 각 깊이에서 2 또는 3 두 가지뿐입니다. split이 매번 최소 2배가 되므로 탐색 깊이는 O(log split_limit)이고, 전체 상태 수는 제한 조건과 분배 노드 한도로 강하게 줄어듭니다. 각 상태에서 수행하는 계산은 상수 시간이므로 실질적으로 매우 작은 탐색량으로 해결됩니다.

핵심 관찰

같은 깊이의 분배 노드는 같은 자식 수를 가지므로 실제 트리 대신 깊이별 자식 수와 현재 확장 후보 수만 추적하면 됩니다. 다음 깊이로 넘길 수 있는 후보는 최대한 넘기는 것이 이후 분기 기회를 보존하므로, 넘길 개수는 min(next_nodes, remain)으로 고정할 수 있습니다.

오답 접근과 반례

현재 깊이에서 리프로 만들 후보를 임의로 많이 확정하면 이후 분배 노드가 부족해질 수 있습니다. next_nodes가 3개이고 남은 분배 한도가 1개라면 3개를 모두 리프로 확정할 것이 아니라 1개를 다음 깊이로 넘겨 그 자식들을 만들 기회를 남겨야 합니다.

3. 문제 해결 코드 (Python)

def solution(dist_limit, split_limit):
    answer = 1

    def search(cur, used, split, leaf):
        nonlocal answer

        if used > dist_limit or split > split_limit:
            return

        # 현재 깊이에서 멈추면 cur도 모두 리프가 됩니다.
        answer = max(answer, leaf + cur)

        for child_count in (2, 3):
            next_split = split * child_count
            if next_split > split_limit:
                continue

            next_nodes = cur * child_count
            remain = dist_limit - used
            next_cur = min(next_nodes, remain)
            next_leaf = leaf + next_nodes - next_cur

            search(next_cur, used + next_cur, next_split, next_leaf)

    # 루트의 자식 하나가 현재 확장 후보인 상태에서 시작합니다.
    search(1, 1, 1, 0)
    return answer

구현 포인트

  • 루트는 자식 하나만 가지므로 초기 확장 후보를 cur=1로 둡니다.
  • 현재 후보를 분배 노드로 확장하려면 분배 노드 한도를 사용하므로 used=1에서 시작합니다.
  • 확장하지 않고 멈추는 경우 현재 후보 cur는 리프가 됩니다.
  • 자식 수가 2 또는 3인 두 경우만 DFS로 탐색합니다.
  • 분배도 곱이 split_limit을 넘으면 해당 경로를 중단합니다.
  • next_cur는 항상 가능한 최대값으로 선택해 미래 확장 기회를 보존합니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 실제 트리를 만들지 않고 깊이별 분기 수와 현재 분배 노드 수만 관리하는 방식으로 문제를 단순화합니다.

완전탐색에서 새로 생긴 노드 중 몇 개를 다음 분배 노드로 넘길지 모두 시도할 수도 있지만, 넘길 수 있는 노드를 줄이면 이후에 만들 수 있는 리프가 줄어듭니다. 이 글에서는 이 관찰을 적용해 분기 수 2·3의 선택만 DFS로 탐색합니다.

마무리

큰 수의 트리를 직접 만들 수 없을 때는 노드 하나하나가 아니라 트리의 규칙을 상태로 압축해야 합니다. 이 문제에서는 깊이별 분기 수와 현재 확장 가능한 노드 수만 관리하고, 미래 선택지를 최대한 남기는 그리디를 결합하면 10억 단위 제한도 작은 DFS로 해결할 수 있습니다.

#DFS#프로그래머스#난이도 4