[프로그래머스] 양과 늑대 (Javascript)

잭슨·2024년 6월 12일

node.js 자바스크립트 프로그래머스

알고리즘 문제 풀이

목록 보기

118/130

문제

[프로그래머스] 양과 늑대

접근법

양의 수와 늑대의 수가 같아지지 않도록 하는 경로를 탐색해야 한다. => DFS를 통해 양과 늑대의 수를 누적하다가 늑대의 수가 양의 수보다 크거나 같아지면 즉시 return 하도록 작성하기
하지만 재귀를 탈출할 때 양과 늑대의 수도 다시 이전 값으로 되돌아가기 때문에 아래와 같은 경우를 처리할 추가적인 방법을 찾아야 한다.

예를 들어 위 그림에서 일반적인 DFS를 수행한다고 가정해보자
```
0 : 양1, 늑대0
    1: 양2, 늑대0
        2: 양2, 늑대1
        4: 양2, 늑대1
            3: 양2, 늑대2 (return)
            6: 양2, 늑대2 (return)
    8: 양1, 늑대1 (return)
```
그럼 위와 같이 0번 노드로 다시 돌아왔을 때, 양의 수가 1이 되기 때문에 8번 노드를 탐색할 때 늑대의 수와 양의 수가 같아지면서 그대로 리턴하게 된다.

하지만 우리가 바라는 것은 1번 노드에서 양을 데려와서 8번 노드를 탐색할때 양2, 늑대1이 되어야 한다. 그리고 자식노드를 탐색하여 양4, 늑대1로 만든 다음 다시 0번 노드로 되돌아와서 다시 1 -> 4 -> 6 -> 5 순서로 노드를 방문하여 양5, 늑대3을 만들어야 한다.

처음에는 위 이미지 처럼 모든 경우의 양과 늑대의 합을 구하려고 했다. 하지만 이 경우 약 17!개의 경우의 수를 모두 확인해야 하기 때문에 시간 초과가 날 것 같았다.

해결방안

다른 블로그를 참고했다.

function solution(info, edges) {
    let answer = 0;
    
    const graph = Array.from(Array(info.length),()=>[]);
    for(const [a,b] of edges){
        graph[a].push(b);
    }
    
    dfs(0,0,0,[0]);
    function dfs(cur,wolf,sheep,nextNodes){
        if(info[cur]) wolf++;
        else sheep++;
        
        if(wolf >= sheep) return;
        answer = Math.max(sheep, answer);
        
        nextNodes = [...nextNodes];
        const curIdx = nextNodes.indexOf(cur);
        nextNodes.push(...graph[cur]);
        nextNodes.splice(curIdx,1); // 현재 노드는 탐색 리스트에서 제외
        
        for(let next of nextNodes){
            dfs(next,wolf,sheep, nextNodes);
        }
    }
    
    return answer;
}