양과 늑대

Cramming An·2022년 5월 5일
0

Code Interview

목록 보기
2/11
post-thumbnail

문제 접근

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 가 다르므로 지역변수(다른 메모리 주소를 참조하도록)로 격리해 사용해야한다.

profile
La Dolce Vita🥂

0개의 댓글