[CodeKata] 프로그래머스(Lv3) : 양과 늑대(KAKAO)

 

🥋 Oooth More!! (Level 3) 

 

 

🧮 풀이

이진트리 문제이기 때문에 난이도가 있을거라고 생각했지만, DFS를 적용해서 풀 수 있었던 문제였다.

 

 

🖇 리뷰

function solution(info, edges) {
    let answer = 1;
    const length = info.length;
    const graph = Array.from({length}, () => []);
    
        
    for(let i = 0; i < edges.length; i++){
        const [from, to] = edges[i];
        
        graph[from].push(to);
    }
    
    const dfs = (current, nextNodes) => {
        let [currentNode, sheep, wolves] = current;
        const newNextNodes = [...nextNodes];
        const index = newNextNodes.indexOf(currentNode);
        
        info[currentNode] ? wolves++ : sheep++
        
        answer = Math.max(answer, sheep);
        
        if(sheep === wolves){
            return;
        }
        
        if(graph[currentNode].length){
            newNextNodes.push(...graph[currentNode]);
        }
        
        newNextNodes.splice(index, 1);
        
        for(const nextNode of newNextNodes){   
            dfs([nextNode, sheep, wolves], newNextNodes);
        }
    }
    
    dfs([0, 0, 0], [0]);
    
    return answer;
}

* 출처 : https://eunchanee.tistory.com/628  

 

1. 풀이 준비

• answer는 최대로 모았던 양의 개수로, DFS가 돌면서 가질 수 있는 양의 최대값을 누적한다.
• graph는 이진트리를 재정리하는 이중배열(길이는 info.length) 로, graph[노드] 번째 배열에 연결된 자식노드들을 저장한다. 
• edges를 순회하면 각 요소는 [from, to] 튜플이다. graph[from]의 배열에 to를 push()해서 넣어준다.

 

2. DFS 설계

• DFS() 함수는 current([현재노드, 양의 수, 늑대의 수]), nextNodes(다음 이동 노드들) 2가지 배열을 인자로 받는다.
• [currentNode, sheep, wolves]로 current 배열을 구조분해하고, newNextNodes는 다음으로 이동할 노드들이다.
• index는 newNextNodes에서 현재노드의 인덱스로, 다음 DFS가 돌기 전에 newNextNodes에서 지워줘야하기 때문이다.
• info[currentNode]를 확인해서 0이면 sheep을, 1이면 wolves 수에 1을 더해준다. 그리고, answer를 현재 sheep 수와 큰 값으로 갱신한다.
• 만약, sheep과 wolves의 수가 같다면 DFS() 를 끝낸다.(return)
• graph[currentNode] 요소가 존재한다는 것은 현재노드의 자식노드가 존재하는 것이다. 이들을 newNextNodes에 push() 한다.
• 현재 newNextNodes에는 현재노드, 누적된 상위노드들의 형제노드들, 현재의 자손노드들이 담겨있다. 형제노드는 다른길로 우회하는 방법, 자손노드는 다음경로를 탐색하는 방법에 해당한다. 현재노드는 splice() 로 지워준다.
• 마지막으로, newNextNodes를 순회하며 DFS()를 돌려준다. current는 [다음노드, 양의 수, 늑대 수], nextNodes는 지금의 newNextNodes를 넣어준다.
• DFS를 처음 시작할 땐, [최상위 노드(0), 0, 0]으로 current를 시작하며, nextNodes에 [0]을 넣어 splice()의 오류를 방지한다.

 

Class까지 제작해야하나 고민했지만, 단순히 DFS로 풀 수 있었다.

특히, nextNodes에 상위노드의 형제노드들이 쌓이는 것을 보며 이진트리 풀이에 매우 유용한 방법이라고 생각했다.