[Javascript/자바스크립트] (프로그래머스) 양과 늑대

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

코드

function solution(info, edges) {
  let answer = 0;

  const n = info.length;
  const graph = Array.from(new Array(n), () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
  }

  const visited = new Array(n).fill(false);

  const bt = (sheep, wolf) => {
    answer = Math.max(answer, sheep);
    for (const [s, e] of edges) {
      if (visited[s] && !visited[e]) {
        if (info[e] === 0) {
          visited[e] = true;
          bt(sheep + 1, wolf);
          visited[e] = false;
        } else if (info[e] === 1 && sheep > wolf + 1) {
          visited[e] = true;
          bt(sheep, wolf + 1);
          visited[e] = false;
        }
      }
    }
  };

  visited[0] = true;
  bt(1, 0);

  return answer;
}

 

`bt()`를 재귀적으로 수행하며 노드를 하나씩 방문하는 풀이이다. 다만, 방문한 노드를 다시 방문할 수 있다는 점을 유의해야 한다.

 

방문할 노드를 고를 때는 다음과 같은 기준을 만족해야 한다.

- 현재 방문한 노드들에서 도달할 수 있어야 한다. (`visited[s]`)

- 아직 방문하지 않은 노드로 가는 것이어야 한다. (`!visited[e]`)

- 해당 노드에 방문했을 때 양의 마릿수가 늑대 마릿수보다 많아야 한다.

---

문제를 이리저리 생각해봐도 해결방법이 잘 떠오르지 않아서 구글링을 해본 문제였는데, 이 풀이의 접근방법이 내가 접근했던 방향과 완전 다른 느낌이라서 갖고 왔다. 

https://velog.io/@thguss/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-L3-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80-python

`bt()`가 한 번 실행될 때마다 하나의 간선을 추가하는 듯한 풀이 방법이 보면 마치 크루스칼 알고리즘 같기도 하다. 그렇지만 간선의 가중치를 정렬한다거나 하는 과정도 없고, MST를 구하는 것이 목적이 아니기 때문에 이건 크루스칼은 아니다.