[알고리즘/프로그래머스/카카오] 양과 늑대

문제

---

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

프로그래머스

 

풀이

---

이진 트리를 탐색하면서 양이 늑대에게 잡아먹히지 않도록 하는 양의 최댓값을 구하는 문제이다. 방문한 늑대 노드의 수가 방문한 양 노드 수 이상인 경우 늑대는 양을 모두 잡아먹는다. 

 

트리 전체를 탐색하면서 방문한 양과 늑대 개수를 세야하고 info의 최댓값도 작기 때문에 DFS 문제이다. 하지만 일반적인 DFS와 다르게 노드를 재방문해야 하는 경로가 있기 때문에 어려웠다. 예를 들어, 예제 1번의 정답 경로인 [0, 1, 8, 7, 9, 4, 6, 5]의 순서로 방문하는 경우, 경로를 살펴보면 0 ->  1 -> 0 -> 8 -> 7 -> 8 -> 9 -> ... 와 같이 방문했던 노드를 재방문하면서 탐색해야하는 것을 알 수 있다.

 

노드를 재방문할 때는 사실상 해당 노드는 그냥 거쳐가는 것일 뿐, 답에 아무런 영향을 미치지 않기 때문에 해당 경로를 통해서 다음으로 방문 가능한 노드만 확인해주면 된다. 이는 nextNodes에 저장하는데, 현재 노드를 제외한 기존 nextNodes(nextNodes.filter(el => el !== cur)와 현재 노드에서 갈 수 있는 다음 노드들(graph[cur])을 합친 배열이다. 

 

DFS로 탐색할 때는 현재 노드, [양 개수, 늑대 개수], 다음 방문할 정점들을 넘겨준다. 현재 노드의 타입(양 or 늑대)에 따라 [양, 늑대] 배열을 증가시켜주고, 양의 수가 maxSheep보다 크면 maxSheep을 갱신한다. 그리고 늑대 수가 양의 수 이상이 되면 모두 잡아먹히므로 이때는 더 이상 탐색하지 않도록 return 처리한다. 그렇지 않다면, 위에서 설명한대로 nextNodes를 구해 다음 하나씩 방문해본다. 

 

이때 주의할 점은 filter 대신 splice를 통해 nextNodes를 구하는 경우, 자기 자신을 포함한 배열([0])을 nextNodes의 초기값으로 넘겨주어야 한다는 것이다. filter로 처리하면 빈 배열을 넘겨줘도 된다. 또한, 양과 늑대의 개수를 배열로 넘겨주는 경우, 값을 복사해서 사용해야 하지 않으면 문제가 생길 수 있어 항상 스프레드 연산자로 복사한 다음 수정해서 사용해야 한다. 

function solution(info, edges) {
    const N = info.length
    const graph = Array.from({ length: N }, () => [])
    let maxSheep = 0
    
    for (let [from, to] of edges) {
        graph[from].push(to)
    }
    
    // 현재 노드, [양, 늑대], 다음 방문할 정점들
    function DFS(cur, count, nextNodes) {
        const [s, w] = [...count]
        const nextCount = info[cur] === 0 ? [s + 1, w] : [s, w + 1]
        
        const [sheep, wolf] = nextCount
        if (maxSheep <= sheep) maxSheep = sheep
        if (sheep <= wolf) return 
        
        // 방문할 노드 리스트에 현재 노드의 자식 노드 넣어주기
        const next = [...nextNodes.filter(el => el !== cur), ...graph[cur]]
 
        for (let node of next) {
            DFS(node, nextCount, next)
        }
        
    }
    
    DFS(0, [0, 0], [])
    return maxSheep
    
}