프로그래머스: 양과 늑대 - javascript(back이 가능한 dfs)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

문제 풀이 힌트 

신박한 문제였다.

자신과 연결된 자식 node로 이동할 수 있는 것은 기본으로 + 다시 부모 노드를 통해 다른 node로 이동이 가능하다.  

 

무슨 말이냐? 

 

문제에 최적의 이동경로가 이렇다고 말해준다. 

 

즉, 0 => 1=> 8 => 7 => 9 => 4 => 6 =>5 의 이동경로라는 것이다. 

이 이동경로를 아래 사진을 눈으로 따라가보자. 

 

기존 이진트리의 부모 노드 => 자식 노드 의 이동 뿐만 아니라 , 

자식 노드 => 부모노드의 이동을 통해 다른 node로 이동하는 것이 가능해진다. 

즉, 부모노드랑 연결된 다른 node를 잊으면 안된다. 

이 부분이 문제의 핵심이 되겠다. 

이걸 구현할 줄 아느냐 못하느냐의 차이이지. 나머지는 그냥 기본 dfs였다. 

 

어떻게 구현하는 것이 좋을까?  '앞으로 갈 수 있는 노드' (부모 노드를 통해 이동할 수 있는 노드 + 내 자식 노드)를 계속 저장해가면서 모든 경우의 수를 탐색한다. 

(늑대수가 양의 수 이상이 되면 그쪽으로 탐색 종료) 

 

현재 노드 0번일 때 

양의 수는 1이다. 앞으로 갈 수 있는 노드는 [1,8]이다. 

 

현재 노드 1일 때 

양의 수는 2이다. 앞으로 갈 수 있는 노드는 [8,2,4]이다. 

 

현재 노드 8일 때 

양의 수는 2이다. (늑대는 1이다.) 앞으로 갈 수 있는 노드는 [2,4,7,9]이다. 

 

현재 노드 2일 때 

양의 수 2, 늑대 2 return 

 

현재 노드 4일 때,

양의 수 2, 늑대 2 return 

 

현재 노드 7일 때, (지금까지 경로: 0 => 1=> 8 => 7)

양의 수 3, 늑대 1이다. 앞으로 갈 수 있는 노드는 [2,4,9]이다. 

 

현재 노드 9일 때, 

양의 수 4, 늑대 1이다. 앞으로 갈 수 있는 노드는 [2,4,10,11]이다. 

 

현재 노드 10일 때, 

양의 수 4, 늑대 2이다. 앞으로 갈 수 있는 노드는 [2,4,11]이다. 

 

...이런식인데, 

생략된 부분이 있을 수도 있고, 그렇다. (요정도만 이해하고 정답 풀이 코드로 더 이해해보자 ! ) 

어찌됐든, 내가 0번 => 1번으로 이동했을 때 이동 가능한 노드를 배열에 담는다. 

부모 노드랑 연결되어있는 노드 8번과 나의 자식 노드 2 번, 4번 다 탐색하는 것이다. 

그때 늑대 수가 양의 수 이상이 되면 그 이상의 탐색을 하지 않고 돌아온다. 

모든 탐색을 하면서 최대 양의 수를 갱신하고, 

모든 탐색이 끝났을 때 max를 return하면 된다. 

 

dfs를 깊게 이해할 수 있는 문제 였다고 생각한다. 

지루한 일 일지라도, 다들 손으로 dfs 흐름을 작성해보는 것이 좋겠다. 

정답 풀이 코드 

function solution(info, edges) {
    let map = new Map(); //연결 노드 edges 정리해둘 객체 생성 
    
    //edges 반복문 돌면서 연결 노드를 정리한다. 
    edges.forEach(([a, b]) => { //a는 부모노드, b는 자식노드 
        if (!map.has(a)) map.set(a, []); //만약 해당 a가 key값으로 없으면 새로 설정한다. 
        map.get(a).push(b); //부모노드 키에 해당하는 값에 접근해서 b를 추가해준다. 
    });
    
    let max = Number.MIN_SAFE_INTEGER; //최대의 양의 수를 갱신해줄 변수 

    //완전 탐색
    function dfs(current, nextNodes, sheep, wolf) {
       info[current] === 0 ? sheep++ : wolf++ //현재 노드가 양이면? 양+1, 아니라면 늑대+1
        if(wolf >= sheep) return; //늑대가 양의 수 이상이 되면 그 탐색은 종료한다. 
        if(max < sheep) max = sheep; //양의 수가 기존 max 값보다 크면 값을 갱신한다. 
        
        let possibleNodes =[...nextNodes, ...(map.get(current)) || []] //이동 가능한 모든 경우의 수이다. 간접적으로 부모 노드를 통해 이동 가능한 node들 + 직접적으로 현재 node와 연결된 자식 노드 
        possibleNodes.splice(nextNodes.indexOf(current), 1) //현재의 node를 possibleNodes에서 삭제해준다. possibleNodes에서 현재 노드의 index는 nextNodes에서의 현재 노드 index와 동일하다. (possibleNodes는 nextNodes 배열부터 ...연산자로 뿌려줬기 때문에)   
        
        for(let next of possibleNodes){ //모든 이동 가능한 node들을 탐색하러 가보자. 
            dfs(next, possibleNodes, sheep, wolf)
        }
    }

    dfs(0, [0], 0, 0); //루트노드는 양, 탐색 가능한 노드 배열, 양의 수, 늑대 수  
    return max;
}

Only 정답 코드 

function solution(info, edges) {
    let map = new Map();
    
    edges.forEach(([a, b]) => {
        if (!map.has(a)) map.set(a, []);
        map.get(a).push(b);
    });
    
    let max = Number.MIN_SAFE_INTEGER;

    function dfs(current, nextNodes, sheep, wolf) {
       info[current] === 0 ? sheep++ : wolf++
        if(wolf >= sheep) return; 
        if(max < sheep) max = sheep; 
        
        let possibleNodes =[...nextNodes, ...(map.get(current)) || []]
        possibleNodes.splice(nextNodes.indexOf(current), 1)
        
        for(let next of possibleNodes){
            dfs(next, possibleNodes, sheep, wolf)
        }
    }

    dfs(0, [0], 0, 0);
    return max;
}