[프로그래머스] 양과 늑대

문제 링크:

https://school.programmers.co.kr/learn/courses/30/lessons/92343

회고:

• 한놈부터 패고보는(?) dfs 특성상 함수로 따로 구현할 필요 없이 stack으로 구현 가능하다. 다만, 한 방향부터 차례대로 팬다면(?) 답에 접근할 수 없다. 접근 가능한 노드들을 하나씩 다 찔러보면서 가능한 깊게 들어가는 것이다. 아래 소스코드에서 possible_nodes가 그 역할을 한다.
• 파이썬에서 Boolean을 정수형으로 나타내면 다음과 같다.

  True -> 1
  False -> 0
  
  ex) 
  1 + True = 2
  1 + False = 1

  
  

python

# 늑대에게 잡아먹히지 않는 최대한 많은 수의 양은 리턴
# 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양이 잡아먹힘
# 0은 양, 1은 늑대
# info[0]은 항상 0(=양)


from collections import defaultdict

SHEEP = 0
WOLF = 1


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

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

    max_sheep = 0

    # dfs를 위한 스택, (현재 노드, 이동가능한 노드, 양의 수, 늑대 수)
    stack = [[0, graph[0], 1, 0]]

    while stack:
        current_node, possible_nodes, sheep_count, wolf_count = stack.pop()

        max_sheep = max(max_sheep, sheep_count)

        for idx, next_node in enumerate(possible_nodes):
            new_sheep_count = sheep_count + (info[next_node] == SHEEP)
            new_wolf_count = wolf_count + (info[next_node] == WOLF)

            if new_sheep_count > new_wolf_count:
                stack.append([
                    next_node,
                    possible_nodes[:idx] + possible_nodes[idx + 1:] + graph[next_node],
                    new_sheep_count,
                    new_wolf_count
                ])

    return max_sheep


if __name__ == "__main__":
    result = solution(
        info=[0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1],
        edges=[[0, 1], [1, 2], [1, 4], [0, 8], [8, 7], [9, 10], [9, 11], [4, 3], [6, 5], [4, 6], [8, 9]],
    )

    print(result)

5