2022 KAKAO BLIND RECRUITMENT에 나왔던 문제이며 레벨3으로 분류되어있다

문제

이진트리로 제시된 초원에서 양보다 늑대가 같거나 많아지지 않게 노드를 돌아다닐 때 가장 많이 얻을 수 있는 양의 갯수를 출력하는 문제이다.
출발점은 무조건 0번노드이며 방문 가능한 노드는 방문한 노드의 하위노드로 제한되지만 방문하는 순서는 제한이 없다.

풀이과정

<입력>

1. 노드번호별로 양인지 늑대인지 정보가 담긴 "info" (Array)
2. 노드 연결 정보가 담긴 "edges" (Array)

<이진트리 정보 그래프화>

우선 입력으로 얻을 수 있는 정보는 간선뿐이기 때문에 연결 정보를 더 효율적으로 표현하기 위해 그래프화한다.

let graph = Array.from({length:info.length},()=>[]) //info 길이가 노드 수기때문에 노드수만큼 배열 생성  
    for(const edge of edges){                       
        graph[edge[0]].push(edge[1])                //출발 node에 도착node 넣어주기
    }

<트리 탐색>

우선 확인할 수 있는 조건 중 유용하게 써먹을 수 있는 조건이 있는데, 양과 늑대의 수가 같아지면 안된다는것이다. 모든 가능성을 끝까지 가볼 필요 없이 경로별로 양과 늑대를 카운트하다가 늑대가 더 많아지면 종료시켜주면 될것같았다.

    let answer=0                          //경로가 종료될때마다 종료시 양의 갯수가 현재보다 많으면 저장해줄것

    function dfs(node, animal, visit){    // node: 방문할노드, animal: [양,늑대], visit:방문가능한 노드들
        info[node]===0?animal[0]++:animal[1]++  //방문할 노드의 정보를 받아서 양인지 늑대인지 카운트 
       
        if(animal[1]>=animal[0]) {              //늑대가 양보다 많으면
            return;                             //경로 종료
        }
        visit.push(...graph[node])                //현재 노드의 하위노드들을 방문예정처리 해주고
        visit.forEach((val,idx,arr)=>{            //모든 방향의 가능성을 탐색해본다.
            let rest = arr.filter((v,i)=>i!=idx)  //어떤 한 노드를 선택하면 그 노드 제외 모든 노드가 다시 선택지가 될 수 있다.
            dfs(val,[...animal],rest)             //다음 노드를 방문하도록 다시 재귀호출
        })
            if(animal[0]>answer) answer=animal[0] //현재 양의 갯수가 정답보다 많으면 정답을 갱신
            return;
    }

그 다음은 0번 node 부터, 초기 양늑대는 [0,0]마리, 방문할node는 아직 없으므로 []를 넣고 함수를 돌려주면 된다.

전체코드

function solution(info, edges) {
let graph = Array.from({length:info.length},()=>[])
    for(const edge of edges){
        graph[edge[0]].push(edge[1])
    }

    let answer=0
    function dfs(node, animal, visit){
        info[node]===0?animal[0]++:animal[1]++

        if(animal[1]>=animal[0]) {
            return; 
        }
        visit.push(...graph[node])
        visit.forEach((val,idx,arr)=>{
            let rest = arr.filter((v,i)=>i!=idx)
            dfs(val,[...animal],rest)
        })
            if(animal[0]>answer) answer=animal[0]
            return;
    }

    dfs(0,[0,0],[])

    return answer
}

결과는?

가능한 모든 경로를 탐색하는것이기에 시간이 꽤 걸릴줄알았지만 생각보다는 양호하게 수행되어서 의외였다.

처음에는 answer를 배열로 만들어서 함수가 종료될때마다 양의 갯수를 answer에 넣고 마지막에 내림차순 정렬해서 제일 처음 값을 출력하는 방법을 썼었는데 테스트케이스 기준 약 30가지 정도 경로가 있었던것같다.
2진트리여서 하위노드 갯수가 제한되어있어서 그런것일까..
더 효율적으로 풀 수 있는 방법이 있는지도 고민해봐야겠다.