프로그래머스) 양과 늑대 with JS

양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

코드

function solution(info, edges) {
  let max = 1;
  let graph = {};
  for (let [a, b] of edges) {
    graph[a] ? graph[a].push(b) : (graph[a] = [b]);
  }

  function DFS(now, sheep, wolf, list) {
    max = Math.max(max, sheep);
    if (sheep <= wolf) return;

    let temp = graph[now] ? [...list, ...graph[now]] : [...list];
    temp.splice(temp.indexOf(now), 1);

    for (let x of temp) {
      if (info[x] === 0) DFS(x, sheep + 1, wolf, temp);
      else DFS(x, sheep, wolf + 1, temp);
    }
  }

  DFS(0, 1, 0, [0]);

  return max;
}

해결 방법

이 문제를 보고 DFS를 활용하고 경우의 수로 왼쪽, 오른쪽, 뒤로 가기 3가지를 생각했다. 하지만 이것은 효율적인 풀이가 아니었다. 결국 구글링을 하고 많은 사람들이 갈 수 있는 노드 리스트를 만들어서 풀고 있는 것을 봤다.

 

  let graph = {};
  for (let [a, b] of edges) {
    graph[a] ? graph[a].push(b) : (graph[a] = [b]);
  }

우선 인접리스트로 각 노드의 자식들을 저장해줬다. 

DFS 함수

    max = Math.max(max, sheep);
    if (sheep <= wolf) return;

    let temp = graph[now] ? [...list, ...graph[now]] : [...list];
    temp.splice(temp.indexOf(now), 1);

DFS 안에서는 sheep의 최대 개수를 max에 계속 비교했고 늑대의 수가 양보다 같거나 많아지면 종료하게 했다.

그리고 temp에는 현재(now) 노드에 있을 때, 갈 수 있는 노드 리스트를 업데이트했다. 그리고 현재 있는 노드는 리스트에서 삭제했다.

    for (let x of temp) {
      if (info[x] === 0) DFS(x, sheep + 1, wolf, temp);
      else DFS(x, sheep, wolf + 1, temp);
    }

갈 수 있는 노드 리스트를 순회하면서 모든 경우의 수를 구했다. 조건은 다음 노드가 늑대일 때, 양일 때로 구분했다.