1. 문제 설명

양과 늑대

2. 문제 분석

DFS를 통해 재귀적으로 백트래킹하는 문제. 중복 방문이 가능하기 때문에 현재 양/늑대의 개수를 파라미터로 전달하면서 최댓값을 갱신한다. 이때 방문하지 않은 상태의 자식 노드가 양인지 늑대인지 info를 통해 확인, 다음 DFS에 넘길 파라미터를 맞춰준다.

• 이때 현재 노드 정보를 가지고 있지 않고 DFS를 돌릴 때마다 모든 간선을 참조하고 있는데, 현 시점에서 '방문' 가능한 자식 노드만 체크한다 해도 이전에 미리 visited 해놓은 곳에서는 아무런 합산이 이루어지지 않기 때문이다.
• 실제로 처음 방문하게 되는 노드 지점을 어떤 순서대로 방문할 것인지가 문제 풀이의 핵심인 셈이다.

3. 나의 풀이

import Foundation

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
    var total = 0
    var visited = Array(repeating: false, count: info.count)
    visited[0] = true

    DFS(1, 0)
    
    func DFS(_ curSheep: Int, _ curWolf: Int) {
        if curSheep <= curWolf {
            return
        } else {
            total = max(total, curSheep)
        }
        
        for edge in edges {
            let parent = edge[0]
            let child = edge[1]
            let nextState = info[child] == 0 ? (1, 0) : (0, 1)
            if visited[parent] && !visited[child] {
                visited[child] = true
                DFS(curSheep + nextState.0, curWolf + nextState.1)
                visited[child] = false
            }
        }
    }
    return total
}