2022 카카오 코딩테스트 lv.3 양과 늑대 파이썬

from collections import deque

def solution(info, edges):
    tree = [[] for _ in range(len(info))]
    for a,b in edges:
        tree[a].append(b)
    q = deque([(1,0,tuple([1]+[0]*(len(info)-1)))])
    visited = set()

    while q:
        s,w,visit = q.popleft()
        if s == w:
            continue
        if (s,w,visit) in visited:
            continue
        visited.add((s,w,visit))

        for i in range(len(info)):
            if visit[i] == 1:
                for j in tree[i]:
                    if not visit[j]:
                        temp = list(visit)
                        temp[j] = 1
                        if info[j] == 0:
                            q.append((s+1,w,tuple(temp)))
                        else:
                            q.append((s,w+1,tuple(temp)))
    return max(visited)[0]

 

이 문제에서 트리는 이동한 경로를 다시 되돌아가 방문하지 않은 곳을 방문할 수 있습니다.

따라서 현재 양, 늑대의 수, 방문한 경로를 visited에 저장합니다.

현재 방문한 노드들에서 이동가능한 방문하지 않은 노드가 있다면, 이동합니다.