[프로그래머스] 양과 늑대 풀이(python)

풀이

• "당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서..."

가장 중요한 점은 방문 순서가 상관이 없다는 점이다. 왜냐하면 방문한 노드의 양과 늑대를 다 더하고 늑대가 많다면 탐색을 잔행 하지 못하기 때문이다. 

• 다시 루트 노드로 돌아오려 합니다."

노드의 재방문을 고민해보면 양방향 간선을 통해서 해결할 수 있다.
이 부분 때문에 2차원 배열의 메모제이션이 필요하다.

• dp는 cache[node][방문한 노드들] = 양의 최대 수

코드

from collections import defaultdict

nodes = []
edges = []
cache = []

def dfs(node, visited):
    global nodes, edges

    sheep = 0
    wolf = 0

    if cache[node][visited] != -1:
        return cache[node][visited]

    #방문 순서에 따른 wolf, sheep
    for i in range(len(nodes)):
        if visited & (1 << i) != 0:
            if nodes[i] == 0:
                sheep += 1
            else:
                wolf += 1

    cache[node][visited] = 0
    if sheep <= wolf:
        return cache[node][visited] 

    cache[node][visited] = sheep
    childes = []

    for edge in edges:
        if edge[0] == node:
            childes.append(edge[1])
        if edge[1] == node:
            childes.append(edge[0])
    
    for child in childes:
        cache[node][visited]  = max(cache[node][visited] , dfs(child, visited | (1 << child)))

    return cache[node][visited] 

def solution(info, edge):
    global nodes, edges, cache

    nodes = info
    edges = edge
    cache = [[-1] * (1 << 17) for _ in range(17)]

    return dfs(0, 1)



if __name__ == "__main__":
    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(solution(info, edges))

 

 

문제

프로그래머스 문제 링크

 

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다.

"당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다."