프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

노드를 직접 만들 수 없는 큰 제한에서 트리 전체를 깊이별 상태 네 개로 압축하고, 자식 수 선택을 DFS로 탐색하면서 다음 깊이에 넘길 노드를 최대화하는 그리디 근거까지 세워야 한다. 상태 설계와 가지치기 규칙을 함께 도출해야 하므로 Level 4로 판단한다.

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)이고, 전체 상태 수는 제한 조건과 분배 노드 한도로 강하게 줄어든다. 각 상태에서 수행하는 계산은 상수 시간이므로 실질적으로 매우 작은 탐색량으로 해결된다.

확장 선택의 상태 보존

search에 들어온 상태에서 cur는 아직 분배할지 리프로 확정할지 결정하지 않은 노드 수다. 이 중 next_cur만 다음 깊이로 넘기고 나머지를 next_leaf에 더하면, 한 깊이의 동일한 자식 수 조건을 지키면서 선택 결과를 숫자 네 개로 보존할 수 있다. next_cur를 남은 한도까지 최대로 잡는 것은 현재 단계에서 리프로 바꾼 노드를 되돌릴 수 없기 때문에, 이후 확장 후보를 버리지 않는 선택이다.

다음 깊이를 남기는 선택

같은 깊이의 분배 노드는 같은 자식 수를 가지므로 실제 트리 대신 깊이별 자식 수와 현재 확장 후보 수만 추적하면 된다. 다음 깊이로 넘길 수 있는 후보는 최대한 넘기는 편이 이후 분기 기회를 보존하므로, 넘길 개수는 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는 항상 가능한 최대값으로 선택해 미래 확장 기회를 보존한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 분배 한도가 없어 바로 리프가 되는 경계를 확인할 수 있다.

assert solution(1, 1) == 1
assert solution(1, 2) == 2

4. 참고 풀이 비교

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

마무리

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

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