🌟 문제
문제 설명
2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.
예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.
각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.
... 프로그래머스 - 양과 늑대
풀이 방법 및 코드
1. edges를 이용해 연결 정보를 저장한다.
2. dfs탐색 진행, current, nextNodes, sheep, wolf를 인자로 넘겨준다.
3. 현재 점이 양인지 늑대인지 체크하고, 카운팅한다.
4. 늑대의 수가 양의 수보다 많다면, return하고
아니라면, 현재의 양의 수와 maxCount를 비교하고 갱신한다.
5. 갈 수 있는 노드들과 자식노드들을 합치고, 현재 노드를 제거한다.
6. 갈 수 있는 노드들로 dfs 탐색을 진행한다.function solution(info, edges) {
let matrix = Array.from(Array(info.length), () => []);
let maxCount = 0;
for (let [from, to] of edges) {
matrix[from].push(to);
}
function dfs(current, nextNodes, sheep, wolf) {
info[current] === 0 ? sheep++ : wolf++;
if (wolf >= sheep) return;
if (maxCount < sheep) maxCount = sheep;
let possibleNodes = [...nextNodes, ...matrix[current]];
possibleNodes.splice(nextNodes.indexOf(current), 1);
for (let next of possibleNodes) {
dfs(next, possibleNodes, sheep, wolf);
}
}
dfs(0, [0], 0, 0);
return maxCount;
}마무리
귀엽지만 너무 사악한 문제다.ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
너무 어려웠다.ㅠㅠ 꼭 다시 풀어봐야겠다!
