풀이 방식

백트래킹을 이용한 탐색방식으로 풀었다. 하지만 현재 어느 곳을 갈 수 있는지 여부를 매개변수로 주어 이전에 늑대의 수가 양의 수 보다 많을 떄 못갔던 곳을 갈 수 있도록 하였다. 즉 늑대의 수가 양의 수보다 더 많거나 같다고 버리는 것이 아니라 저장해 놨다가 나중에 탐색을 할 수 있도록 하기 위함이였다. 이 때문에 양방향이 아니라 단방향 그래프 만으로 해결이 가능하였다.

코드

from collections import defaultdict
from collections import deque
def dfs(dq,scnt,wcnt):
    global answer
    wtmp_list = list()
    answer = max(scnt,answer)
    for i in range(len(dq)):
        p = dq.popleft()
        if infos[p] == 1:
            if scnt>wcnt+1:
                for j in D[p]:
                    dq.append(j)
                dfs(dq,scnt,wcnt+1)
                for j in D[p]:
                    dq.pop()
        else:
            for j in D[p]:
                dq.append(j)
            dfs(dq,scnt+1,wcnt)
            for j in D[p]:
                dq.pop()
        dq.append(p)
    
def solution(info, edges):
    global answer,infos,D
    infos = info # 양, 늑대 여부
    answer = 0
    D = defaultdict(list) # 그래프
    dq = deque()
    for i in edges:
        D[i[0]].append(i[1])
    dq.append(0)
    dfs(dq,0,0)
    return answer