백준 1697 숨바꼭질

DFS가 아닌 BFS인 이유

• 그래프를 그려보며 느낀 건 DFS일 경우 로직 낭비가 심해진다
• 최단거리니까 당연히 BFS라고 생각하기보단 그래프를 그려보면서 생각해봤음

부가 설명

• visited 배열을 동생의 위치 크기로 해주려 했으나 그거로는 모자라겠다 생각했고 그냥 주어진 입력만큼으로 해보았는데 됐다 !!.. 100,000이 아닌 100,001인 이유는 index로 위치를 인식하기 위함
• for of문을 저런식으로 사용하면 next변수를 오른쪽 배열의 연산 결과의 변수로 사용할 수 있음

const fs = require('fs');
const input = fs
  .readFileSync('example.txt')
  .toString()
  .trim()
  .split(' ')
  .map((el) => +el);

const N = input.shift();	//수빈위치
const K = input.shift();	//동상위치

//방문 배열 생성
const visited = Array.from({ length: 100001 }, () => false);

const bfs = (start, end) => {
  const queue = [];
  //queue에는 수빈이의 위치와 움직인 횟수를 같이 담아준다
  queue.push([start, 0]);
  //방문처리
  visited[start] = true;
  while (queue.length !== 0) {
    //지금의 위치와 x로 구조분해할당
    //x가 의미하는건 시간 문제를 참고
    const [curN, x] = queue.shift();
    if (curN === end) return x;
    //움직일 수 있는 세가지의 연산을 해준 값을 nextN으로 초기화해준다
    for (const nextN of [curN + 1, curN - 1, curN * 2]) {
      //방문하지 않았어야 하고 AND nextN이 0이랑 같거나 커야하고 AND visited의 length를 벗어나면 안된다
      if (!visited[nextN] && nextN >= 0 && nextN <= visited.length) {
        //조건을 모두 만족하면 queue에 추가해주고 방문처리 해주고 반복
        queue.push([nextN, x + 1]);
        visited[nextN] = true;
      }
    }
  }
};

console.log(bfs(N, K));