drop-of-water

문제 링크

조건

  • 루트 노드에는 항상 양이 있음 (answer 최소값 1)
  • 늑대의 수가 양의 수보다 같거나 크면 모든 양을 잡아먹음

입력값

  • info = 각 노드에 양 (0) 이 있는지 늑대 (1) 가 있는지에 대한 정보 (배열)
  • edges = 각 노드들의 연결 관계를 저장하고 있음 (2차원 배열) ([0,1] = 1은 0의 child 노드)

출력값

  • 모을 수 있는 최대 양의 개수

풀이과정

  • DFS를 사용해 모든 경우의 수를 확인 한다
  • 주어진 노드들의 연결 관계를 2차원 배열을 사용해 그래프 형태로 저장한다
  • 각 노드들을 traverse 하면서 양의 수와 늑대의 수를 더한다
  • 늑대의 수가 양의 수보다 같거나 크면 return
  • 늑대의 수가 양의 수보다 작으면 최대 양의 수를 업데이트 한 후 현재 노드의 child 들을 다음에 확인할 노드 배열에 push 하고 현재 노드를 해당 배열에서 삭제한다

코드

function solution(info, edges) {
  // 루트 노드에는 항상 양이 있음 (answer 최소값 1)
  let answer = 1;
  const graph = Array.from(Array(info.length), () => []);

  const solve = (cur, nextNodes) => {
    let [curNode, sheep, wolf] = cur;
    const newNextNodes = [...nextNodes];
    const curIdx = newNextNodes.indexOf(curNode);

    sheep += !info[curNode];
    wolf += info[curNode];

    // 늑대의 수가 양의 수보다 같거나 크면 모든 양을 잡아먹음
    if (sheep <= wolf) {
      return;
    } else {
      // 최대 양의 수를 업데이트 한 후
      answer = Math.max(answer, sheep);

      //현재 노드의 child 들을 다음에 확인할 노드 배열에 push 하고
      newNextNodes.push(...graph[curNode]);

      //현재 노드를 해당 배열에서 삭제한다
      newNextNodes.splice(curIdx, 1);

      for (const nextNode of newNextNodes) {
        solve([nextNode, sheep, wolf], newNextNodes);
      }
    }
  };

  for (let i = 0; i < edges.length; i++) {
    const [parent, child] = edges[i];
    graph[parent].push(child);
  }

  solve([0, 0, 0], [0]);

  return answer;
}

😊