[JS] 양과 늑대

첫 단추를 많이 헤매서 푸는데 어려운 문제였다.

 

처음에는 재귀를 활용해서 트리를 한번만 순회하는 구조로 풀어보려고 했다.

 

재귀의 반환 값을 배열로 두고, 배열의 n번째를 n개의 양을 투입하였을때 얻을 수 있는 양의 개수.. 로 두고 문제를 해결하려고 했다. 해당 방법으로는 트리를 한번만 순회할순 있었지만 내가 그 양을 얻을때 필요한 늑대의 개수를 생각할수가 없었다. 

 

 

문제의 힌트는 트리의 크기가 17개로 제한된다는 점에서 사실 있었다.

 

트리의 크기가 17개밖에 안되게 제한된다는건 사실 완전탐색으로 풀어보라는 의미가 컸다...

 

 

dfs의 인자로 현재 탐색할 node,양의개수,늑대의개수,현재 내가 탐색할 수 있는 노드의 수를 설정한다.

 

위 방법대로 해결하면 dfs로 탐색하는 방법 중에 단순히 노드를 한번씩 방문하는 것이 아닌, 노드를 방문하는 순서까지 고려해서 노드들을 방문하는 모든 경우의 수를 고려할 수 있다.

 

이때 늑대의 개수가 양의 개수 이상이라면 탐색할 필요가 없는 노드이기에 방문을 하지 않는다.

 

 

 

 

 

function solution(info, edges) {
  const graph = [...Array(info.length)].map((_) => []);
  for (const [start, end] of edges) {
    graph[start].push(end);
  }

  let ret = 0;
  const dfs = (node, sheep, wolf, possible) => {
    // console.log('node',node,'possible',possible,'sheep',sheep,'wolf',wolf)
    ret = Math.max(ret, sheep);
    if (sheep <= wolf) return;

    const possibleNode = [...possible, ...graph[node]];
    possibleNode.splice(possibleNode.indexOf(node), 1);

    for (const nxNode of possibleNode) {
      if (info[nxNode]) dfs(nxNode, sheep, wolf + 1, possibleNode);
      else dfs(nxNode, sheep + 1, wolf, possibleNode);
    }
  };

  dfs(0, 1, 0, [0]);
  return ret;
}