[PS] 양과 늑대

문제 링크

코드

def solution(info, edges):
    graph = {x: set() for x in range(len(info))}
    for s, d in edges:
        graph[s].add(d)
        graph[d].add(s)
        
    
    def backtracking(cur, visited, adj, nsheep, nwolf):
        if info[cur] == 0:
            nsheep += 1
        else:
            nwolf += 1
            
        if nsheep <= nwolf:
            return nsheep
        
        visited = visited | {cur}
        adj = (adj | graph[cur]) - visited
        
        if not adj:
            return nsheep
        return max(map(lambda x: backtracking(x, visited, adj, nsheep, nwolf), adj))
        
        
    return backtracking(0, set(), set(), 0, 0)

리뷰

• 어려운 문제는 아니었지만 쉽게 구현하지 못하고 햇갈렸다.