[2022 KAKAO BLIND RECRUITMENT] 양과 늑대

문제 설명

프로그래머스

---

풀이 방법

• 접근 방식

    ◦  특별한 수학적 규칙이 존재하지 않는다. 노드를 돌면서 양의 수가 최대가 되는 경우를 찾는 탐색 문제이다.

 

• 핵심 아이디어

    ◦  문제에서 제시된 트리의 형태는 이진 트리이나, 매 분기마다 방문 가능한 노드는 자식 노드 단 두개가 아닌 현재 방문한 노드의 모든

         자식 노드라는 점이 포인트

          -  즉 방문한 노드와 방문하지 않은 노드를 관리하기 위한 배열이 필요하다.

    ◦  이를 단순하게 생각해서, 존재하는 모든 노드 관계를 훑으면서 부모는 방문했는데 자식은 방문을 안했다면 바로 방문하는 식으로

         파고 들어가는 DFS 로직을 작성하면 된다.

    ◦  늑대의 수가 양보다 더 많아지면 그 이후로 양의 수는 양수가 될 수 없으므로, 더이상 DFS 트리를 파고들어 갈 필요가 없다.

         바로 재귀를 종료해주자.

 

• 알고리즘

    ◦  DFS 트리

          -  단 탐색 트리의 형태(각 노드의 자식의 개수)가 일정하지는 않다.

---

파이썬 코드

def solution(info, edges):
    # 방문한 노드를 기록하는 리스트
    visited = [0] * len(info)
    visited[0] = 1
    answer = []
    
    def dfs(sheep, wolf, visited):
        # 양과 늑대의 수에 따른 상태 집계
        if(sheep > wolf):
            answer.append(sheep)
        else:
            return
        
        # 방문할 노드가 남아있는 경우
        for i in edges:
            if(visited[i[0]] == 1 and visited[i[1]] == 0):
                newVisited = visited.copy()
                newVisited[i[1]] = 1
                
                # 새로 방문한 노드의 양/늑대 집계
                if(info[i[1]] == 1):
                    dfs(sheep, wolf+1, newVisited)
                else:
                    dfs(sheep+1, wolf, newVisited)
                
    # return answer
    dfs(1,0,visited)
    return max(answer)