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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

dfs를 활용해야 하는 문제인데 조금 특이한(?) dfs 방식을 적용해야하는 문제입니다. dfs 동작은 다음과 같이 일어나게 됩니다.

 

1. 현재 양의 수가 늑대의 수보다 많은지 체크

      1-1. 늑대의 수가 더 많다면 탐색을 종료

2. 방문 가능한 노드 리스트에 현재 노드의 자식들을 추가

3. 노드 리스트들에 대해 탐색 시작

위와 같이 동작해야하는 이유는 다음과 같습니다.

 방문 순서에 따라서 현재 노드를 방문할 수 있는지가 달라질 수 있습니다. 위 그림에서 (0 -> 1 -> 8)은 가능하지만 (0 -> 8 -> 1)은 불가능합니다. 따라서 현재 노드에 도착했을 때 방문 가능한 노드들은 모두 탐색을 해야합니다. 그리고 이가 가능한 이유는 지금까지 방문했던 노드들을 다시 재방문해도 달라지는 것이 없기 때문입니다. 한번 방문을 한 순간 늑대들과 양들이 따라 오기 때문에 다시 방문해도 해당 노드에는 양이나 늑대가 없는 상태이기 때문에 언제든 방문이 가능한 노드로 넘어가서 탐색이 가능하게 됩니다. 이처럼 지금까지 방문한 노드들에 따른 방문 가능한 모든 노드들을 탐색하면서 최대 양의 수를 얻을 수 있습니다.

 

소스코드

from collections import defaultdict

def dfs(cur, sheep, wolf, nodes):
    global g_info, max_ans, graph
    sheep += g_info[cur] ^ 1
    wolf += g_info[cur]

    if sheep <= wolf:
        return 0

    max_ans = max(max_ans, sheep)

    next_nodes = nodes + graph[cur]

    for next_node in next_nodes:
        dfs(next_node, sheep, wolf, [i for i in next_nodes if i != next_node])


def solution(info, edges):
    global g_info, max_ans, graph
    g_info = info
    max_ans = -1

    graph = defaultdict(list)

    for s, e in edges:
        graph[s].append(e)

    dfs(0, 0, 0, [])

    return max_ans