[Refresh ! 코딩 테스트 / js] -양과 늑대

문제풀이

1. 늑대와 양의 갯수가 같은경우 > 이길은 틀린길입니다.
2. 일반적 dfs 는 아님
3. 여기서 0-2-5-1 << 1을 어떻게 갈수 있을까? 이부분이 제일 헷갈렸다.
   3-1 이전에 많이 풀던 dfs 는 push & pop 형식으로 visited 하지 않은 길을 push 하여서 한번에 갔던 길은 다시 가지 않는식으로 처리했었음
   3-2 그럼 전에는 가지 못했던 1번 늑대를 어떻게 갈수 있는지를 푸는 문제이다.

문제해석
1. dfs + backtracking 문제라고 한다.
2. 즉 예전에는 갈수 없는 노드를 push 하지 않아서 못갔지만. 이제는 갈수도 있으니 우선을 넣어보자 가 되버린다
3 . 그러니 backtracking 을 유지하기 위해서는 기본 while 구조문으로 도는것 보다 재귀문으로 함수를 이동하는것이 더쉽다.
4. 예를들면
0: [1,2]
1: 가봤더니 안됨
2: [1,5,6]
2-1 2-> 1: 이제는 갈수 있음 [5,6,3,4] ~-> 갈수 있고
2-2 2->5 : [1,6]
이런식으로 여러가지 갈래가 나오게 된다. 따라서 이 후보군들을 유지시키면서 가야되기때문에. 재귀문으로 후보군을 유지시키면서 가는게 더 편하다.

나의코드

function solution(info, edges) {
    var answer = 0;
    let obj={};
    edges.forEach((ek)=>{
        let[parent,child]=ek;
        if(!obj[parent]) obj[parent]=[child];
        else obj[parent].push(child);
    })
    
    const dfs= function(start,fox,sheep,candidate){
        
        info[start]==0?sheep+=1:fox+=1;
        if(fox==sheep)return;
        answer= Math.max(answer,sheep);
        
        let new_candidate=[...candidate];
        
        if(obj[start]){
            new_candidate.push(...obj[start])
        }
        
        new_candidate.splice(new_candidate.indexOf(start),1);
        for(const start_go of new_candidate ){
            dfs(start_go,fox,sheep,new_candidate)
        }
        
        
    }
    dfs(0,0,0,[0])
    
    
    return answer;
}

3일동안 고민했는데 어찌 저찌 풀었다...^^ ㅠ 남의 코드도 열심히 봤다...