Programers / Level 3 / 양과 늑대 / JS

문제 간단설명

"양과 늑대" 문제는 트리 구조에서 양과 늑대를 관리하며 최대한 많은 양을 모으는 문제입니다.

 

제한 사항

• 2 <= info의 길이 <= 17
  • info의 원소는 0 또는 1입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다.
    즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행)의 길이 = info의 길이 - 1
  • edges의 가로(열)의 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로,
    서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못도니 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

 

성공 코드

/**
 * 주어진 정보와 엣지를 기반으로 최대 양의 수를 계산합니다.
 * @param {number[]} info - 각 노드가 양인지 늑대인지 나타내는 배열 (0: 양, 1: 늑대)
 * @param {number[][]} edges - 그래프의 엣지를 나타내는 배열 (각 엣지는 [from, to] 형태)
 * @returns {number} - 가능한 최대 양의 수
 */
function solution(info, edges) {
  const SHEEP = 0;
  const WOLF = 1;

  const graph = Array.from({ length: info.length }, () => []);

  let maxSheepCount = 0;

  /**
   * 엣지를 기반으로 그래프를 초기화합니다.
   * @description 이 함수는 전역 변수 `graph`를 엣지 정보로 채워 트리 구조를 생성합니다.
   */
  const initGraph = () => {
    for (const [from, to] of edges) {
      graph[from].push(to);
    }
  };

  /**
   * 깊이 우선 탐색을 통해 가능한 모든 경로를 탐색하며 양의 수를 최대화합니다.
   * @param {number} curNode - 현재 탐색 중인 노드의 인덱스
   * @param {number} sheepCount - 현재까지 만난 양의 수
   * @param {number} wolfCount - 현재까지 만난 늑대의 수
   * @param {Set<number>} possibleVisitSet - 방문 가능한 노드의 집합
   * @description 이 함수는 재귀적으로 호출되며, 늑대 수가 양의 수 이상이 되지 않는 경로에서 최대 양의 수를 계산합니다.
   */
  const dfs = (curNode, sheepCount, wolfCount, possibleVisitSet) => {
    let nextSheepCount = sheepCount;
    let nextWolfCount = wolfCount;

    if (info[curNode] === SHEEP) {
      nextSheepCount++;
    } else {
      nextWolfCount++;
    }

    if (nextWolfCount >= nextSheepCount) {
      return;
    }

    maxSheepCount = Math.max(maxSheepCount, nextSheepCount);

    // 원본이 수정되는것을 막기 위해 복사를해서 사용합니다.
    const nextPossibleVisitSet = new Set(possibleVisitSet);
    // 현재 노드는 방문중이므로 방문 가능한 노드 Set에서 삭제합니다.
    nextPossibleVisitSet.delete(curNode);

    for (const adjNode of graph[curNode]) {
      nextPossibleVisitSet.add(adjNode);
    }

    for (const nextPossibleNode of nextPossibleVisitSet) {
      dfs(
        nextPossibleNode,
        nextSheepCount,
        nextWolfCount,
        nextPossibleVisitSet
      );
    }
  };

  initGraph();
  dfs(0, 0, 0, new Set());

  return maxSheepCount;
}

 

기본 DFS 문제들과 비슷하지만, 하나 추가된게 있다면 갈 수 있는 후보 노드들을 저장해놔야 한다는 것이다.

중복되면 안되므로 Set 자료구조를 이용했는데, 그냥 배열로 처리해도 상관은 없다.

다만, 어떤 자료구조를 이용해도 조심해야 할 것은 같다.

다음 재귀를 진행하기 위해 인자를 넘기기 위해 현재 재귀에서 사용했던 자료구조를 그대로 넘기면 안된다.

배열이나 Set 등의 자료구조를 그냥 넘기게 되면 주소값을 넘기게 되므로, 원본이 바뀌기 때문이다.

따라서 복사해서 로직을 진행 한 후, 복사한 것을 넘겨줘야 한다.