[프로그래머스] 양과 늑대 - Level 3 (Python)

📌 문제 정보

양과 늑대 Level 3

플랫폼

프로그래머스

유형

DFS, BFS, 트리

언어

Python 3

풀이 시간

약 90분

풀이 날짜

2026.05.06

문제 링크

바로가기 ↗

---

🧩 문제 요약

루트가 양인 이진 트리에서, 루트부터 출발해 인접한 노드로 이동하며 늑대에게 잡아먹히지 않는 선에서 모을 수 있는 최대 양의 수를 구하는 문제

규칙 조건:

• 루트 노드(0번)는 항상 양이며, 시작 지점
• 이동은 현재까지 방문한 노드와 인접한 모든 노드 중에서 선택 가능 (트리 경로 순서를 그대로 따라가지 않아도 됨)
• 어떤 시점이든 늑대 수 ≥ 양 수가 되는 순간 모든 양이 잡아먹힘 → 그 경로는 더 이상 진행 불가
• 모든 노드를 다 방문할 필요는 없음

입력 조건:

• info: 노드별 양(0)/늑대(1) 정보 배열, 1 ≤ info의 길이 ≤ 17
• edges: 트리의 간선 정보 [부모, 자식] 쌍의 배열

출력 조건:

• 잡아먹히지 않고 모을 수 있는 양의 최댓값(int)

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

부모-자식 정보(info, edges)를 보고 일단 트리 구조부터 파악했다. {노드: 부모, 종류} 형태로 직접 정리해보면서 0번이 항상 양이고, 시작점이라는 것부터 확인했다.

2단계 - 막혔던 부분

"어떻게 이동하면서 양을 셀 것인가"가 핵심이었는데, 처음엔 단순히 트리를 따라 내려가면 되는 줄 알았다. 하지만 **"지금 갈 수 있는 노드 목록"**을 계속 들고 다녀야 한다는 게 이해가 안 됐다. 특히 한 번 방문한 노드의 자식이 아직 안 간 상태로 목록에 계속 남아있다는 점, 그리고 트리 부모-자식 순서를 꼭 지키지 않고 열려있는 노드 아무 곳이나 갈 수 있다는 점이 헷갈렸다.

3단계 - 해결 실마리

next_nodes(또는 visited)라는 **"아직 방문하지 않았지만 갈 수 있는 노드 집합"**을 상태로 들고 다니면 된다는 걸 깨달았다. 새 노드를 방문하면:

1. 그 노드의 자식들을 next_nodes에 추가
2. 그 중 하나를 선택해서 다음 상태로 넘어가되, 선택한 노드는 next_nodes에서 제거

이 패턴을 BFS(큐)로도, DFS(재귀)로도 구현해봤다. 둘 다 **"늑대 ≥ 양이 아닌 모든 경로를 끝까지 탐색하며 최댓값을 갱신"**하는 동일한 아이디어였다.

핵심 아이디어:

• next_nodes = next_nodes + tree[node]로 방문 가능한 목록을 계속 누적
• 선택한 노드는 [n for n in next_nodes if n != next_node]로 제외하고 다음 상태에 전달
• sheep <= wolf(또는 wolf >= sheep)이면 그 경로는 return 0 또는 continue로 즉시 차단
• 모든 경로를 다 탐색한 뒤, 그 중 가장 컸던 양의 수를 반환

---

✅ 최종 풀이 코드 (DFS)

from collections import defaultdict


def solution(info, edges):
    tree = defaultdict(list)

    for parent, child in edges:
        tree[parent].append(child)

    def dfs(node, sheep, wolf, next_nodes):
        if info[node] == 0:
            sheep += 1
        else:
            wolf += 1

        if sheep <= wolf:
            return 0

        next_nodes = next_nodes + tree[node]
        max_sheep = sheep

        for next_node in next_nodes:
            result = dfs(
                next_node, sheep, wolf, [n for n in next_nodes if n != next_node]
            )
            max_sheep = max(max_sheep, result)

        return max_sheep

    return dfs(0, 0, 0, [])

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(N²)	노드 수 N개에 대해, 매 호출마다 next_nodes를 순회하며 새 리스트를 만드는 연산([n for n in next_nodes if n != next_node])이 O(N) → 전체 O(N²)
공간 복잡도	O(N)	next_nodes 리스트, 재귀 콜스택 모두 노드 수 N에 비례

info의 길이가 최대 17로 작기 때문에, O(N²)이어도 충분히 빠르게 동작한다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	BFS 큐 초기값을 (0, 1, 0, pc[0])로 설정 → 루프 안에서 next_nodes + pc[node]를 또 더하게 되어 시작 노드의 자식이 중복으로 들어감	초기값을 (0, 1, 0, [])로 비워서 시작, 루프 안에서 pc[0]이 한 번만 더해지도록 수정
2차	next_nodes.remove(next_node)로 처리 → 원본 리스트를 직접 수정해버려서 같은 for문의 다음 반복에서 목록이 망가짐	[n for n in next_nodes if n != next_node]로 새 리스트를 만들어 원본은 보존
3차	통과 ✅	-

---

🔄 다른 풀이 방법

BFS (큐 기반)

from collections import defaultdict, deque


def solution(info, edges):
    pc = defaultdict(list)
    max_sheep = 1
    for p, c in edges:
        pc[p].append(c)

    queue = deque([(0, 1, 0, [])])
    while queue:
        node, sheep, wolf, next_nodes = queue.popleft()
        if wolf >= sheep:
            continue

        next_nodes = next_nodes + pc[node]
        for next_node in next_nodes:
            new_next = [n for n in next_nodes if n != next_node]
            new_sheep = sheep + (1 if info[next_node] == 0 else 0)
            new_wolf = wolf + (1 if info[next_node] == 1 else 0)
            max_sheep = max(max_sheep, new_sheep)
            queue.append((next_node, new_sheep, new_wolf, new_next))

    return max_sheep

DFS vs BFS 비교:

• DFS: 한 경로를 끝까지 파고든 뒤(재귀), 돌아오면서(return) 위쪽 호출에 결과를 전달 → 경로/상태 추적에 자연스러운 구조
• BFS: 큐에 (노드, 양 수, 늑대 수, next_nodes) 상태 전체를 통째로 저장해서 순서대로 꺼내며 탐색 → 원래 BFS는 "레벨/거리" 탐색에 쓰이는데, 이 문제에서는 상태를 큐 원소에 욱여넣어 쓰는 형태라 다소 부자연스러움
• 결과적으로 이 문제는 경로 단위 상태 추적이 핵심이라 DFS가 더 직관적인 구조

BFS (Set 활용)

from collections import deque


def solution(info, edges):
    def build_tree(info, edges):
        tree = [[] for _ in range(len(info))]
        for edge in edges:
            tree[edge[0]].append(edge[1])
        return tree

    tree = build_tree(info, edges)
    max_sheep = 0

    q = deque([(0, 1, 0, set())])

    while q:
        current, sheep_count, wolf_count, visited = q.popleft()
        max_sheep = max(max_sheep, sheep_count)
        visited.update(tree[current])

        for next_node in visited:
            if info[next_node]:
                if sheep_count != wolf_count + 1:
                    q.append(
                        (next_node, sheep_count, wolf_count + 1, visited - {next_node})
                    )
                else:
                    q.append(
                        (next_node, sheep_count + 1, wolf_count, visited - {next_node})
                    )
    return max_sheep

리스트 vs set 비교:

• 리스트 버전(next_nodes): [n for n in next_nodes if n != next_node]로 매번 전체 순회하며 새 리스트 생성
• set 버전(visited): visited - {next_node}로 차집합 연산, 표현이 더 간결하고 중복 노드 자동 제거
• 둘 다 내부적으로 O(N) 복사 연산이 들어가므로 시간복잡도는 동일하게 O(N²)

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: 이 문제의 핵심은 "트리를 부모-자식 순서대로 내려가는 것"이 아니라, **방문한 노드들의 자식을 모두 모아둔 "갈 수 있는 노드 집합"**을 들고 다니며 그 안에서 자유롭게 선택해 이동하는 것이다. 트리 형태를 빌렸을 뿐 실제로는 상태 공간 탐색에 가깝다.
• ✏️ 새로 알게 된 것: DFS의 재귀는 "내려갈 때 깊이 파고들고, 올라올 때 최댓값을 위로 전달"하는 구조다. max_sheep = sheep은 현재 경로의 최소 보장값이고, 이후 max(max_sheep, result)로 더 깊은 탐색 결과와 비교하며 갱신된다.
• ⚠️ 실수했던 점: 리스트 remove()는 원본을 직접 수정한다는 걸 놓쳐서, 같은 for문 안에서 다음 반복을 할 때 목록이 의도치 않게 변형되는 버그가 있었다. 새 리스트를 만드는 리스트 컴프리헨션으로 바꿔서 해결했다.
• 💬 한 줄 요약: 트리 모양에 속지 말고, "지금까지 열려있는 선택지 집합"을 상태로 들고 다니는 탐색 문제로 보면 풀린다!