dfs
를 이용한 완전탐색으로 풀이가 가능하나..
최대한 많은 수의 양들을 지켜야하므로 무작정 깊이 탐색을 하면 안된다.
양을 발견시 처음 노드로 돌아오도록 한다면, 같은 level에 있는 양도 찾을 수 있으므로 최대한 양을 많이 모을 수 있다.
단, 한 번 방문한 양과 늑대의 node 값은 모두 지워주어야 중복된 양이나 늑대의 수의 덧셈을 피할 수 있다. 나는 info
배열에서 방문한 양과 늑대 노드값을 -1
로 만들어 주었다.
탐색 마다, 트리의 노드값을 바꾸고, 연결되어 있는 엣지를 따라 깊이 탐색하면서 노드 값에 따라 노드를 점프(?)해서 탐색하는 재밌는 문제이다.
function solution(info, edges) {
const answerArr = []
const dfs = (sheep, wolf, info, node) => {
edges.forEach((edge) => {
let [start, end] = edge
if (start === node) {
const endInfo = info[end]
if (endInfo === 0) {
let newSheep = sheep
newSheep += 1
answerArr.push(newSheep)
const newInfo = [...info]
newInfo[end] = -1
dfs(newSheep, wolf, newInfo, 0)
} else {
let newWolf = wolf
const newInfo = [...info]
if (endInfo === 1) {
newWolf += 1
newInfo[end] = -1
}
if (sheep > newWolf) {
dfs(sheep, newWolf, newInfo, end)
}
}
}
})
}
info[0] = -1
answerArr.push(1)
dfs(1, 0, info, 0)
answerArr.sort((a, b) => b - a)
return answerArr[0]
}
주의할 점은,
노드마다 가지고 있는 sheep, wolf, info, node 가 다르므로 지역변수(다른 메모리 주소를 참조하도록)로 격리해 사용해야한다.