2022 KAKAO BLIND RECRUITMENT에 나왔던 문제이며 레벨3으로 분류되어있다
이진트리로 제시된 초원에서 양보다 늑대가 같거나 많아지지 않게 노드를 돌아다닐 때 가장 많이 얻을 수 있는 양의 갯수를 출력하는 문제이다.
출발점은 무조건 0번노드이며 방문 가능한 노드는 방문한 노드의 하위노드로 제한되지만 방문하는 순서는 제한이 없다.
우선 입력으로 얻을 수 있는 정보는 간선뿐이기 때문에 연결 정보를 더 효율적으로 표현하기 위해 그래프화한다.
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진트리여서 하위노드 갯수가 제한되어있어서 그런것일까..
더 효율적으로 풀 수 있는 방법이 있는지도 고민해봐야겠다.