문제 보기 · Level 3 · 2022 KAKAO BLIND RECRUITMENT · 정답률 43% · 푼 사람 9,150명 (2026-09-30 기준)1
문제
이진 트리의 노드마다 양 또는 늑대가 한 마리 있다. 루트(항상 양)에서 출발해 트리를 따라 자유롭게 오가며 노드를 방문하고, 방문한 노드의 동물을 모은다. 모은 늑대 수가 양 수 이상이 되는 순간 양을 모두 잃는다. 모을 수 있는 양의 최대 수를 돌려준다.
- 노드 2~17개
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 재귀와 백트래킹: 다음에 갈 노드를 하나씩 골라 들어가 본다.
- 비트 연산과 비트마스크: “지금까지 방문한 노드들”을 수 하나로 기억해 같은 상태를 다시 보지 않는다.
- 집합: 방문한 노드들은 순서를 따지지 않는 모음이다. 노드 n개의 부분집합은 멱집합의 크기인 2ⁿ개뿐이다.
1단계 · 작은 예로 손으로 풀기
루트 0(양)의 자식이 1(늑대)과 2(양), 1의 자식이 3(양)이라고 하자.
- 시작: 양 1, 늑대 0. 지금 갈 수 있는 곳: 1, 2
- 2(양)부터 간다 → 양 2, 늑대 0. 갈 수 있는 곳: 1
- 1(늑대)로 간다 → 양 2, 늑대 1(2 > 1이라 괜찮다). 갈 수 있는 곳: 3
- 3(양)으로 간다 → 양 3
답은 3이다. 처음에 1(늑대)로 먼저 가면 양 1, 늑대 1이라 바로 잡아먹힌다. 순서가 중요하다.
“자유롭게 오간다”는 말은, 이미 방문한 노드에 붙은 자식이면 언제든 갈 수 있다는 뜻이다. 되돌아가는 길은 이미 방문한 노드뿐이라 동물이 더 늘지 않는다.
2단계 · 가장 단순한 방법과 그 속도
“지금 갈 수 있는 노드 목록”을 들고 다니며, 목록의 노드를 하나씩 골라 들어가는 재귀가 먼저 떠오른다. 이 방법은 방문 순서마다 따로 돈다. 루트에 양 노드 k개가 바로 붙은 트리에서 재귀 호출 수를 재 보니 k = 9에서 약 99만 번이었다. k!에 비례해 늘어서 k = 16이면 끝나지 않는다.
그런데 결과(양·늑대 수, 다음에 갈 수 있는 곳)는 순서가 아니라 방문한 노드들의 집합만으로 정해진다. 집합은 많아야 2¹⁷ = 131,072개다.
3단계 · 핵심 아이디어
- 상태 = 방문한 노드 집합: 노드 i를 방문했으면 i번 자리가 1인 수(비트마스크)로 나타낸다.
- 다음에 갈 수 있는 노드: 아직 방문하지 않았고, 부모는 방문한 노드다. 노드를 “부모가 먼저”인 부분순서로 보면, 이 노드들은 아직 안 간 노드 가운데 극소 원소다. 방문 순서는 위상 정렬의 앞부분이다.
- 갈 수 있는지: 그 노드의 동물을 더한 뒤 양 > 늑대여야 한다.
- 같은 상태는 한 번만: 이미 본 비트마스크면 바로 돌아간다. 같은 집합에 다른 순서로 도착해도 그 뒤는 똑같기 때문이다.
- 방문한 적 있는 상태들에서의 양 수 중 최댓값이 답이다.
4단계 · 코드 흐름
- 노드마다 부모 번호를 적어 둔다.
- go(방문 집합, 양, 늑대): 이미 본 집합이면 돌아간다. 아니면 기록하고 최댓값을 고친다.
- 방문하지 않았고 부모가 방문된 노드 v마다, v의 동물을 더해 양 > 늑대면 go(집합 | v, …).
- go(루트만, 1, 0)을 부르고 최댓값을 돌려준다.
5단계 · 파이썬 코드
def solution(info, edges):
n = len(info)
parent = [-1] * n
for p, c in edges:
parent[c] = p
best = 0
seen = set()
def go(mask, sheep, wolf):
nonlocal best
if mask in seen: # 같은 집합은 한 번만
return
seen.add(mask)
best = max(best, sheep)
for v in range(n):
# 아직 안 갔고(v번 자리 0), 부모는 갔다(부모 자리 1)
if not (mask >> v) & 1 and (mask >> parent[v]) & 1:
s = sheep + (info[v] == 0)
w = wolf + (info[v] == 1)
if s > w:
go(mask | (1 << v), s, w)
go(1, 1, 0) # 루트(0번)만 방문, 양 1마리
return best
(mask >> v) & 1: v번 노드를 방문했으면 1이다.mask | (1 << v): v번 자리를 켠 새 집합이다.- 루트(v = 0)는 처음부터 방문되어 있어 앞 조건에서 걸러진다. 그래서
parent[0] = -1로 밀기(>> -1)를 할 일이 없다. sheep + (info[v] == 0): 참(True)은 1, 거짓(False)은 0으로 더해진다.
6단계 · 실행 추적
1단계의 트리(0 양, 1 늑대, 2 양, 3 양)
| 방문 집합 | 양 | 늑대 | 다음 후보 | 갈 수 있나 |
|---|---|---|---|---|
| {0} | 1 | 0 | 1(늑대), 2(양) | 1은 1 > 1이 아니라 안 됨, 2는 됨 |
| {0, 2} | 2 | 0 | 1(늑대) | 2 > 1이라 됨 |
| {0, 1, 2} | 2 | 1 | 3(양) | 됨 |
| {0, 1, 2, 3} | 3 | 1 | 없음 |
최댓값은 3이다.
7단계 · 복잡도와 흔한 실수
상태(방문 집합)가 많아야 2ⁿ개이고 상태마다 노드 n개를 보니 \(O(2^n \cdot n)\), n = 17이면 약 220만 번이다.
- “다음에 갈 수 있는 곳”을 자식 노드만으로 좁힌다. 방문한 어떤 노드의 자식이든 갈 수 있다.
- 늑대 수가 양 수와 같아도 잡아먹힌다는 점을 놓친다(
s > w여야 한다). - 같은 집합을 다른 순서로 여러 번 돌아 시간이 폭발한다.