[JS] 양과 늑대

문제

프로그래머스

 

풀이

이번 문제는 단방향 그래프를 이용해 탐색을 진행할 것이다. 양방향 그래프 탐색을 생각도 해봤지만, 양방향을 사용하게 되면 모든 경로를 다시 처리해야하는 번거로움이 있기 때문에 단방향 그래프를 이용했다.

 

DFS 알고리즘을 적용했으며, 각 탐색시 현재 위치, 양의 수, 늑대의 수, 방문할 노드를 전달한다. 이때 알고 가야하는 로직이 있는데, 방문할 노드를 결정할 때 방문할 노드에 있는 현재 노드를 현재 노드의 자식 노드들로 바꿔주어야 한다. 그래야지 중복으로 노드를 방문하지 않고 완전탐색을 진행할 수 있기 때문이다.

 

코드

function solution(info, edges) {
  let answer = 0;
  const map = Array.from({ length: info.length }, () => []);
    
  edges.forEach(([p, c]) => {
    map[p].push(c)
  });
    
  const dfs = (curIdx, sheep, wolf, arr) => {
    info[curIdx] ? wolf++ : sheep++;
    if (answer < sheep) answer = sheep;
    
    if (sheep <= wolf) {
      return;
    }
        
    for (let i = 0; i < arr.length; i++) {
      const t = arr[i];
      dfs(t, sheep, wolf, [...arr.filter(e => e !== t), ...map[t]]);
    }
    return;
  }
  dfs(0, 0, 0, map[0]);
    
  return answer;
}