[BFS] 송아지 찾기

🚩 송아지 찾기

 

📖 문제 설명 : 현수가 -1, +1, +5칸을 움직일 수 있다. 최소 몇 번의 이동으로 송아지가 위치한 곳 까지 갈 수 있는지 구해라.

 

💡 +1을 간 경우에서 -1을 수행할 경우 똑같은 위치를 반복해서 탐색하는 경우가 있다. 따라서 방문 표시를 위한 체크 배열을 이용한다.

 

// 송아지 찾기 (BFS: 상태트리탐색)

function solution(S, E) {
  let answer = 1 // 연산 편의를 위한 1부터 시작
  let queue = [S] // 처음 나의 위치
  let visited = [] // 중복 숫자 처리를 위한 방문 처리 배열

  while (true) {
    let tmp = []

    let n = queue.length // queue.shift 할 경우 길이가 반복문 수행시 달라짐
    for (let i = 0; i < n; i++) {
      let firstQueue = queue.shift()
      // 방문한적 없는 숫자일 경우만 계산을 위한 tmp 배열 삽입 및 방문 처리
      if (!visited.includes(firstQueue)) {
        tmp.push(firstQueue)
        visited.push(firstQueue)
      }
    }

    // 점프 연산
    for (let j = 0; j < tmp.length; j++) {
      queue.push(tmp[j] - 1)
      queue.push(tmp[j] + 1)
      queue.push(tmp[j] + 5)
    }

    // E 값이 있을 경우 송아지 찾기 완료
    if (queue.includes(E)) {
      console.log(queue)
      break
    }
    answer += 1
  }

  return answer
}

console.log(solution(5, 14)) // 3
console.log(solution(8, 3)) // 5

👨‍💻 코드 설명

1. 현재 현수의 위치를 queue에 삽입해 준다.

 

2. 송아지를 찾을 때까지 반복문을 수행한다.

 

3. queue에 있는 값을 꺼내 방문하지 않았던 위치의 경우 방문 표시를 해주고, 해당 위치에서 -1, +1, +5 연산을 수행한 위치를 넣어준다.

 

4. queue에서 송아지의 위치가 있을 경우 찾았기 때문에 반복문을 종료하고 그렇지 않으면 이동 횟수를 카운트해주고 3번의 과정을 다시 수행한다.

 

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.