[프로그래머스]Lv3. 양과 늑대(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

문제 접근

 

못 풀더라도 문제나 이해하자.

 

1. 양의 수가 늑대의 수보다 많은가? => 탐색 조건?

2. 이미 방문한 노드인가? => 체크

3. 처음 방문한 노드인가?

 

양이 늑대보다 많으면 양의 수를 결과 배열에 저장해서 max값 리턴

 

DFS 사용

1. 현재까지 탐색한 양의 수, 늑대 수를 인자로 받기
2. 탐색 시작 전, 양의 수가 늑대 수보다 많은지 확인
3. edges 배열을 순회하며, 부모 노드가 방문한 상태이고 자식 노드가 미방문 상태이면
   
   1. 자식 노드를 방문 상태로 변경 후 양, 늑대 여부로 dfs 재귀 호출
   2. 재귀가 끝나면 다시 미방문 상태로 변경

코드

def solution(info, edges):
    # 각 노드의 방문 여부 체크 
    visited = [0] * len(info)
    
    answer = []
    
    # 현재 양의 수, 늑대의 수
    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] = 1
                
                if info[c] == 0:    # 자식이 양이면
                    dfs(sheep+1, wolf)
                else: 
                    dfs(sheep, wolf+1)
                visited[c] = 0
        
    visited[0] = 1  # 루트 노드부터 탐색 시작 
    dfs(1, 0)
     
    return max(answer)