문제 링크

프로그래머스 문제

풀이

dfs로 푸는건 확실해 보였다. 하지만 그 다음 노드로 들어갈때, 어떻게 관리하냐가 중요했다.
지금까지 풀었던 경험으로는 node에 방문후 다시 재방문은 항상 막아두었기 때문에 특히나 어려웠다.
이번 문제 풀이에서 가장 중요했던 부분은 possibleNodes를 둠으로써 내가 트리의 다른 위치에 가더라도
갈 수 있는 node들을 리스트화 시켜서 만들어 두었다는 것이다.

이전의 분기점으로 되돌아가는것이 아닌 선형적으로 쭉 연결되어 진행하는것,

코드

function solution(info, edges) {
    var answer = 0;
    const visited = new Array(info.length).fill(false)
    const graph = new Array(info.length).fill(0).map(() => new Array())
    
    for(let i=0; i< edges.length; i++){
        const [root , end] = edges[i];
        graph[root].push(end)
    }
    const dfs = (curNode , sheep , wolf, possibleNodes) => {
        // 종료 조건
        
        if(sheep <= wolf){
            return 
        }
        answer = Math.max(answer, sheep)
        
        possibleNodes = [...possibleNodes , ...graph[curNode]];
        possibleNodes.splice(possibleNodes.indexOf(curNode),1);
        
        
        for(const nextNode of possibleNodes){
            if(info[nextNode]) dfs(nextNode , sheep, wolf+1 , possibleNodes)
            else dfs(nextNode, sheep+1, wolf, possibleNodes)
        }
        
        
    }
    dfs(0,1 , 0,  [0])
    
    return answer;
}