Level 3 양과 늑대 <2022 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 

코딩테스트 연습 - 양과 늑대

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_양과늑대.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import defaultdict
def dfs(node, sheep, wolf, visit, can_go):
    global answer, infos, tree
    visit[node] = 1
    can_go += tree[node]
    
    if infos[node]: wolf += 1
    else: sheep += 1
    
    if wolf >= sheep: return
    if sheep > answer: answer = sheep
    
    for n in can_go:
        go = [nn for nn in can_go if nn != n and not visit[nn]]
        dfs(n, sheep, wolf, visit[:], go)
    
    
def solution(info, edges):
    global answer, infos, tree
    infos = info
    answer = 0
    tree = defaultdict(list)
    for p, c in edges:
        tree[p].append(c)
        
    visit = [0]*len(info)
    dfs(0, 0, 0, visit, [])
    
    return answer

---

풀이 과정

from collections import defaultdict
def dfs(node, sheep, wolf, visit, can_go):
    global answer, infos, tree
    
    #현재 노드 방문 처리
    visit[node] = 1
    #현재 노드의 자식 노드들을 can_go에 추가한다
    can_go += tree[node]
    
    #현재 노드에 있는 늑대나 양 카운팅
    if infos[node]: wolf += 1
    else: sheep += 1
    
    #늑대가 양보다 많으면, 더이상 탐색하지 않는다
    if wolf >= sheep: return
    
    #현재 양의 수가 최댓값이라면 갱신
    if sheep > answer: answer = sheep
    
    #갈 수 있는 노드로 탐색을 이어간다
    for n in can_go:
    	#노드n을 can_go에서 제외해준다
        go = [nn for nn in can_go if nn != n and not visit[nn]]
        dfs(n, sheep, wolf, visit[:], go)
    
    
def solution(info, edges):
    global answer, infos, tree
    infos = info
    answer = 0
    
    #tree[p] = p의 자식 노드 번호
    tree = defaultdict(list)
    for p, c in edges:
        tree[p].append(c)
        
    visit = [0]*len(info)
    dfs(0, 0, 0, visit, [])
    
    return answer