문제 링크

풀이 과정

• 노드를 방문해야, 양을 획득할 지 늑대를 획득할 지 알 수 있습니다.
  • 즉, 노드를 방문하기 이전에 양을 최대로 모을 수 있는 방법을 알아낼 수 없습니다.
  • 따라서, 완전 탐색 방식으로 접근해야 합니다.
• 완전 탐색을 위한 고려 사항은 다음과 같습니다.
  • 백트래킹 기준 → 현재 양의 수와 늑대의 수가 같은가?
  • 다음에 방문 가능한 노드를 찾는 방법
    • 출발지 노드는 방문한 상태이며, 목적지 노드는 아직 방문하지 않았는지 확인
  • 최대로 얻을 수 있는 양의 수를 계산하는 방법
    • 각 탐색 경로마다 얻을 수 있는 양의 수를 계산합니다.
    • 서바이벌 방식으로 최댓값을 갱신합니다.

전체 코드

def solution(info, edges):
    '''
    1. 각 노드를 탐방하면서 현재까지 모은 양과 늑대의 수를 체크
        - 양의 수와 늑대 수가 같다면, 해당 경로는 탐방 종료
    2. 방문한 노드를 다시 방문할 수 있도록(양을 얻기 위해서) 처리
    - 노드 탐험 가능 여부?
    - 연결된 노드 간 자유롭게 이동
    
    DFS
    task: 현재 노드에서 최대한 모을 수 있는 양의 수를 구하는 것
    다른 노드에 위임할 것
    1) 종료 조건 확인: 양의 수와 늑대 수가 같은지?
    2) 현재까지 얻은 양의 수를 저장
    3) 탐험 가능한 노드 탐색 후, DFS 재귀 호출
    4) 3)번에서 찾은 노드를 다시 방문할 수 있게 0 처리
    '''       
    def dfs(cur_sheep, cur_wolf):
        nonlocal sheep
        if cur_sheep == cur_wolf:   return
        if cur_sheep > sheep:   sheep = cur_sheep

        for start, end in edges:
            if visited[start] == 1 and visited[end] == 0:
                visited[end] = 1
                if info[end] == 0:  dfs(cur_sheep+1, cur_wolf)
                else:   dfs(cur_sheep, cur_wolf+1)
                # 목적지 노드는, 다른 탐색 경로를 통해 다시 방문할 수 있습니다.
                # 따라서, 깊이 우선 탐색이 끝났을 때 visited 값을 0으로 합니다.
                visited[end] = 0
    
    sheep, wolf = 1, 0
    visited = [0 for _ in range(len(info))]
    visited[0] = 1           
    dfs(sheep, wolf)
    
    return sheep