[프로그래머스 / Python] 양과 늑대

양과 늑대

🔍 알고리즘 분류

• DFS

💡 문제 풀이

• 아래 두 가지 조건만 확인해주면서 DFS 진행하면 됨
  1. 양의 개수 > 늑대의 개수
  2. 부모 노드 방문 & 자식 노드 미방문

📄 코드

def solution(info, edges):
    answer = []
    visited = [False] * len(info)
    
    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        else:
            return
        for p, c in edges:
            # 부모 노드 방문한 적 있으면서 자식 노드 처음 방문
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheep + 1, wolf)
                else:
                    dfs(sheep, wolf + 1)
                visited[c] = False # 백트래킹
    
    visited[0] = True
    dfs(1, 0)
    
    return max(answer)

• 시간복잡도: O(2^N)