[백준] 1697: 숨바꼭질 - JS (그래프 탐색(DFS&BFS))

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

이번에는 BFS로 풀려고 한다. 

 

구현 전에 설정한 조건은 다음과 같다.

• 방식: BFS (queue)
• 이동: -1, +1, *2
• 방문 체크: push 후 해당 요소를 1로 바꿈
• 범위: 100000
• while문
  • 조건: queue.length
  • queue 에는 [item(이동), time]이 한 노드임
  • item과 K가 같다면 출력 후 반복문 종료
  • push 조건
    • - 1: item - 1 >= 0 && arr[item - 1] == 0
    • + 1: item + 1 <= 100000 && arr[item + 1] == 0
    • * 2: item * 2 <= 100000 && arr[item * 2] == 0

 

어차피 0~100000 까지의 숫자라서 굳이 해당 요소를 넣지 않아도 되니 바로 -1, +1 *2를 한 값을 바로 노드의 item에 넣어준다.

그리고 -1, +1, *2 한 동작이라고 할 경우 time은 +1이 된다.

 

초기에 queue.push([N, 0])을 넣는다. 이 경우 N == K 라면 바로 반복문이 종료되고 time인 0이 출력 될 것이다.

 

 

 

  풀이

 

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0].split(" ")[0]);
let K = Number(input[0].split(" ")[1]);    
  
  const arr = new Array(100001).fill(0);
  
  
  const queue = [];

  queue.push([N, 0]);
  
  while(queue.length){
  
    const [item, time] = queue.shift();
  
    if(item == K){
      console.log(time);
      break;
    }
  
    if(item - 1 >= 0 && arr[item - 1] == 0){
      queue.push([item - 1, time + 1]);
      arr[item - 1] = 1;
    }
    if(item + 1 <= 100000 && arr[item + 1] == 0){
      queue.push([item + 1, time + 1]);
      arr[item + 1] = 1;
    }
    if(item * 2 <= 100000 && arr[item * 2] == 0){
      queue.push([item * 2, time + 1]);
      arr[item * 2] = 1;
    }
    
  }