[프로그래머스] Lv.3 양과 늑대 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92343
• 2022 KAKAO BLIND RECRUITMENT
• 카카오 해설 사이트 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/
• 🔑 : DFS

 

def solution(info, edges):
    answer = []

    visit = [0] * len(info)
    visit[0] = 1

    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        else: return

        for p, c in edges:
            if visit[p] and not visit[c]: # 부모 노드는 방문했고 자식 노드는 안갔으면
                visit[c] = 1
                if info[c] == 0: # 자식 노드가 양이면
                    dfs(sheep+1, wolf)
                else:
                    dfs(sheep, wolf+1)
                visit[c] = 0

    dfs(1, 0)

    return max(answer)