[프로그래머스] 양과 늑대

문제

프로그래머스

입력

info:[Int] = i번째 자리에 0이면 양, 1이면 늑대를 나타내는 정보 배열
2 ≤ info의 길이 ≤ 17

_ edges:[[Int]] = [[부모 노드, 자식노드],...] 로 간선에 연결된 부모자식 노드의 정보를 담고 있다. 
2 ≤ info의 길이 ≤ 17

출력

result = 담을 수 있는 최대 양의 마리 수

양 ≤ 늑대 마리 수가되면 지금까지 담은 양은 모두 잡아 먹힌다.

해석

1. 제약 조건은 간단하게 양의 수가 많을 때만 다음 늑대로 갈 수 있다.

2. 또한 들어오는 순서에 따라 이전에 방문할 수 없었던 지점을 다시 방문할 수 있기때문에 백트래킹을 생각할 수 있다.

코드

import Foundation

var answer = -1



func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
    
    // 방문 여부를 나타내는 배열
    var visited: [Bool] = [Bool](repeating: false, count:info.count)
    

    func dfs(_ sheeps: Int,_ wolves: Int) {
        
        if sheeps > wolves {
           answer = max(answer, sheeps)
        }  else { // 양이 적가나 같으면 잡혀먹으니 return 
            return 
        }

        for edge in edges {
            
            let parent = edge[0]  
            let child = edge[1]
            
            // 백트래킹
            if visited[parent] && !visited[child] { // 부모가 방문하지 못했으면 child으로 방문하지 못함
                visited[child] = true
                if info[child] == 0 { // 양이면 다음 dfs에 sheeps+1 
                    dfs(sheeps+1,wolves)
                } else { // 늑대면 wolves+1
                    dfs(sheeps,wolves+1)
                }
                 visited[child] = false 
            }
            
        }
        

    }
    
    visited[0] = true 
    dfs(1,0)
    
    return answer
}