완전탐색 - 양과 늑대(2022 KAKAO BLIND RECRUITMENT)

 

1. 문제

문제는 아래와 같다. 
결국, 늑대에게 잡아 먹히지 않고 최대한 많은 양을 모으고 그 양의 수를 리턴 해야 하는 문제이다.

 

2. Idea 💡

해당 문제에서 키 포인트는 갔던 길을 다시 돌아서 다른 곳으로 갈 수 있다는 것이다. 
예를 들어, 1번 -> 8번 -> 7번 -> 9번 -> 5번 과 같은 방식으로도 이동이 가능하다는 것이다. 

 

이렇게 되면 결국 모든 경우의 수를 탐색하여 각 노드에서 얻을 수 있는 양의 최대 수를 리턴 해야 한다.
단, 만약 해당 노드를 방문했을 때, 양들이 늑대에게 잡아 먹히게 된다면, 해당 노드를 물리고, 다음 노드를 탐색한다.(Backtracking)

 

 

3. Solution

완전 탐색을 하는 방법으로는 가장 크게 dfs(depth first search), bfs(breadth first search)가 있다. 

나는 해당 문제에 접근하기에는 bfs로 접근하는 것이 편리 할 것 같아 bfs로 접근 하기로 했다.

 

 

1. 현재 노드, 지나오면서 자식노드로 등록한 노드들 을 각각 currentNode, queue 라고 명명하자.

2. 현재 노드의 자식노드들을 queue에 넣어주자.

3. 현재 노드에서 방문 가능한 노드들(queue에 남아 있는 노드들)에 대해 bfs를 실시해주자.
    이를 통해, 모든 경우의 수를 탐색 할 수 있게 된다.

 

예를 들어보자. 위의 문제에서
우리는 가장 먼저 0번 노드를 방문하게 된다. 
0번 노드에는 양이 있다. sheep += 1을 해주고, 방문 가능한 노드를 찾자.
0번 노드에서 방문 가능한 노드는 1번 노드와 8번 노드이다. 
이제, 1번과 8번 노드를 queue에 넣어 두자. ([1, 8])(이때, 1번과 8번 노드는 앞으로 언제든지 방문 가능한 노드가 되는 것이다.)
이때, 모든 경우의 수를 탐색해야 하기 때문에, 우리는 0번 ->  1번으로 가는 경우와, 0번 -> 8번으로 이동하는 경우를 모두 재귀적으로 실행시켜 주자.

bfs가 먼저 실행된 1번 노드부터 방문하자. 
1번 노드 역시 양이 있다. sheep +=1을 해주고, 방문 가능한 노드를 찾자. 
1번 노드에서 방문 가능한 노드는 2번 노드와 4번 노드이다. 
2번과 4번을 queue에 넣어주자. [8, 2, 4]
이때 방문 가능한 모든 경우의 수를 탐색해야 하기에, 0번 -> 1번 -> 8번 / 0번 -> 1번 -> 2번 / 0번 -> 1번 -> 4번 으로 가는 모든 경우를 
재귀적으로 실행시켜 주자. 

...

위와 같은 방식으로 탐색을 하되, 만약 해당 노드를 방문시 sheep <= wolf가 되게 되면 return 하여 재귀를 종료한다.

 

 

참고로 나는 가장 처음 이 문제를 접했을 때, 현재 노드에서 방문 가능한 노드를 찾는 부분을 재귀문 안에 넣었었다. 
하지만, 이렇게 되면 매번 edges 배열을 전체 탐색하기 때문에 비효율적이다. 

이렇게 할 필요 없이, HashMap과 같이 가장 처음 edges를 for문을 돌면서 미리 각각의 자식 노드가 무엇이 있는지 배열로 만들어 버리고
이를 그래프 처럼 이용하는 것이 훨씬 효율적이다. 

 

4. 전체 코드

function solution(info, edges) {
  //최대 양의 숫자
  var maxSheep = 0;
  const length = info.length;
  //각 노드에 방문가능 한지여부 판단
  let connectedNode = Array.from({ length }, () => []);

  //결국 DP문제다.
  // 각 노드에 가지고 갈 수 있는 최대 양의 개수를 구하고, 그 값을 answer과 비교하여 return 한다.
  // 연결된 자식노드에

  function bfs(currentNode, sheep, wolf, queue) {
    console.log("currentNode", currentNode, "queue", queue);
    const position = queue.indexOf(currentNode);
    queue = queue.slice();
    if (info[currentNode]) {
      wolf += 1;
    } else {
      sheep += 1;
    }

    if (wolf === sheep) return;
    maxSheep = Math.max(sheep, maxSheep);
    //1. 현재 위치 노드와 연결된 자식 노드들을 queue에 넣어준다.
    if (connectedNode.length) {
      queue.push(...connectedNode[currentNode]);
    }
    queue.splice(position, 1);
    for (let node of queue) {
      bfs(node, sheep, wolf, queue);
    }
  }

//재귀에 들어가기 이전 가장 먼저 hashMap형식으로 graph를 만드는 과정
  for (let i = 0; i < edges.length; i++) {
    const [from, to] = edges[i];
    if (connectedNode[from]) {
      connectedNode[from].push(to);
    } else {
      connectedNode[from] = [to];
    }
  }

  bfs(0, 0, 0, [0]);
  return maxSheep;
}