Algorithm
[CodeKata] 프로그래머스(Lv3) : 양과 늑대(KAKAO)
ttaeng_99
2022. 4. 2. 19:25
반응형
🥋 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에 상위노드의 형제노드들이 쌓이는 것을 보며 이진트리 풀이에 매우 유용한 방법이라고 생각했다.
반응형