(프로그래머스 KAKAO JS)양과 늑대

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

코딩테스트 연습 - 양과 늑대

 

 

 

완전 탐색.

우선 0번째 노드는 항상 양이 있기 때문에 answer = 1로 시작한다.

length는 info의 길이로, 노드의 개수가 된다.

graph는 각 노드에서 자식 노드가 있으면 자식 노드의 번호를 배열 형태로 저장한다.

 

먼저 for문으로 edges를 순회하여 각 노드의 자식 노드를 삽입해준다.

 

이후 dfs 탐색 진행.

인자로는 크게 2개로,

current : [현재 방문한 노드 번호, 양의 수, 늑대의 수]

nextNodes : [다음에 방문할 노드의 번호]

로 넘겨준다.

 

- dfs 함수

우선 current 배열에서 spread 연산으로 각각 currentNode, sheep, wolves로 값을 저장했다.

nextNodes를 새로운 배열 값으로 저장하기 위해 newNextNodes를 선언해 새로 저장했다.

index는 newNextNodes에서 현재 currentNode의 인덱스 값을 저장한다.(무조건 있다)

 

현재 노드 번호와 info를 이용해 양의 수와 늑대의 수를 카운팅한다.

카운팅을 하면 answer와 양의 수를 비교해 더 큰 값을 answer에 저장한다.

 

만약 양의 수가 늑대의 수와 같아진다면 더 이상 진행할 수 없기 때문에 바로 return.

 

그렇지 않다면 계속 다음 노드를 탐색한다.

만약 현재 방문한 노드의 자식 노드가 있다면 newNextNode에 자식 노드의 번호를 추가해준다.

그리고 newNextNode에서 현재 노드의 번호를 지운다.

 

마지막은 newNextNode를 순회하여

dfs 탐색을 계속 진행하면 된다.

 

function solution(info, edges) {
    let answer = 1;
    const length = info.length;
    const graph = Array.from({length}, () => []);
    
    const dfs = (current, nextNodes) => {
        let [currentNode, sheep, wolves] = current;
        const newNextNodes = [...nextNodes];
        const index = newNextNodes.indexOf(currentNode);
        
        sheep += !info[currentNode];
        wolves += info[currentNode];
        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);
        }
    }
    
    for(let i = 0; i < edges.length; i++){
        const [from, to] = edges[i];
        
        graph[from].push(to);
    }
    
    dfs([0, 0, 0], [0]);
    
    return answer;
}