[프로그래머스] 양과 늑대 | 자바스크립트 | Lv.3 | 2022 KAKAO BLIND RECRUITMENT | DFS

문제

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

코딩테스트 연습 - 양과 늑대

 

풀이

function solution(info, edges) {
  const tree = Array.from({ length: info.length }, () => []);
  for (const [parent, child] of edges) tree[parent].push(child);

  let answer = 0;
  function dfs(node, sheep, wolf, possible) {
    answer = Math.max(answer, sheep);
    if (sheep <= wolf) return;

    const possibleNode = [...possible, ...tree[node]];
    possibleNode.splice(possibleNode.indexOf(node), 1);

    for (const next of possibleNode) {
      if (info[next]) dfs(next, sheep, wolf + 1, possibleNode);	// 늑대일 경우
      else dfs(next, sheep + 1, wolf, possibleNode);	// 양일 경우
    }
  }
  dfs(0, 1, 0, [0]);

  return answer;
}

이 문제 너무 어려웠다.. 그냥 dfs로 하면 이전에 방문했던 곳을 어떻게 또 방문하지 ..? 싶었다..

하나씩 풀이해보면, 먼저 parent의 인덱스에 각각 [왼쪽, 오른쪽] 자식을 넣어준다. -> tree
아래 예시 사진으로 설명하겠다.

위에서 보면  0 -> 1 -> 8 -> 7 -> 9 -> 4 -> 6 -> 5 이 순서대로 가야 양의 최대값이 나온다. 

function dfs(node, sheep, wolf, possible) {
    answer = Math.max(answer, sheep);
    if (sheep <= wolf) return;

    const possibleNode = [...possible, ...tree[node]];
    possibleNode.splice(possibleNode.indexOf(node), 1);

    for (const next of possibleNode) {
      if (info[next]) dfs(next, sheep, wolf + 1, possibleNode);
      else dfs(next, sheep + 1, wolf, possibleNode);
    }
}

dfs를 들어오면 sheep개수를 계속해서 반영해준다. 만약 sheep보다 wolf의 개수가 크거나 같으면 리턴한다.

이제 매개변수로 들어온 possible과 현재 node의 자식노드들을 합쳐줄 것이다. possible은 말 그대로 아직까진 방문할 수 있는 노드들을 뜻한다. 만약 2노드를 들어갔다 왔어도 wolf의 개수가 많아서 종료됐다면 2는 아직 방문의 가능성이 있는 노드가 된다. -> possibleNode를 반복문 돈다고 해서 꼭 노드가 사라지는게 아님. (나의 큰 착각이였음. dfs를 들어갔다오면 각 노드가 꼭 사라진다고 인지해버렸다. if (sheep <= wolf) return; 이 조건에 걸리면 안사라짐.)

앞서 가능성 있는 노드들과 현재 node의 자식노드를 합친 다음, 현재 node는 방문을 했으므로 possibleNode에서 제거한다.(splice) 그리곤 양일 경우와 늑대일 경우를 나눠서 카운트를 조절해주면 된다.

---

방문한 현재 node와 possibleNode를 순차적으로 보는게 사실 이해가 빠르다.

// console.log(node, possibleNode)
0, [ 1, 8 ]
1, [ 8, 2, 4 ]
8, [ 2, 4, 7, 9 ]
2
4
7, [ 2, 4, 9 ]
2, [ 4, 9 ]
4
9, [ 4, 10, 11 ]
4, [ 10, 11, 3, 6 ]
10
11
3
6

0: 1, 8의 자식노드가 방문 가능한 노드이다.
1: 본인 1은 제거하고 전달받은 8과 본인의 자식노드 2, 4가 가능성 있는 노드이다.
8: 본인 8은 제거하고 전달받은 2, 4와 본인의 자식노드 7, 9가 가능성 있는 노드이다.
2: wolf가 더 커지거나 같으므로 바로 리턴된다.
4: 마찬가지.
7: 본인 7은 제거하고, 8번째 노드에서 그대로 전달받은 2, 4, 9가 가능성 있는 노드이다.
2: 위의 2와 다르게 sheep의 개수가 늘어서 왔으므로 2도 방문할 수 있다. 본인2는 제거하고, 7에서 전달받은 4, 9가 가능성 있는 노드이다.
4: return
9: 본인 9는 제거하고, 2에서 전달받은 4와 본인의 자식노드 10, 11이 가능성 있는 노드이다.
4: 여기서부터 생략 ...

 

다음부터는 쉽게 풀었으면 한다.. 난 사실 아직도 재귀가 익숙치 않다 ..ㅎ; 평생 친해지고 싶지 않은 친구다.