[백준 알고리즘] Node.js 1697. 숨바꼭질

1. 문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

2. 풀이

1) 수빈이가 있는 위치 N, 도착해야할 위치 K가 주어진다.

2) 수빈이가 움직일 수 있는 경우의 수는 x-1, x+1, x*2 인 3가지이고, 모두 1초가 소요된다.

3) 가장 빠른 시간을 구하는 것이기에 bfs 사용.

 

처음 풀이

const [N,K] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);
const visited = new Array(100001).fill(false);

const bfs = (n,k) => {
  const queue = [[n, 0]];
  while (queue.length) {
    const [pos, t] = queue.shift();
    if (visited[pos]) {
      continue;
    }

    visited[pos] = true;
    if (pos === k) {
      console.log(t);
      break;
    }

    if (pos * 2 <= 100000) {
      queue.push([pos * 2, t + 1]);
    }
    if (pos + 1 <= 100000) {
      queue.push([pos + 1, t + 1]);
    }
    if (pos - 1 >= 0) {
      queue.push([pos - 1, t + 1]);
    }
  }
}

bfs(N,K)

- 처음엔 위치 변화를 각각 다른 if문에 걸어서 사용했다. vscode에서는 정상적으로 작동하는데 백준에 제출했을 때는 1% 도 통과하지 못했다.

 

2차 풀이

const [N,K] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(v => +v);
const visited = new Array(100001).fill(false);

const bfs = (n,k) => {
  const queue = [];
  queue.push([n, 0]);

  while(queue.length){
    const [cur, time] = queue.shift();

    if(visited[cur]) continue;

    if(cur === k) {
      console.log(time);
      break;
    }

    const nx = [cur - 1, cur + 1, cur * 2];

    for(let i = 0; i < nx.length; i++){
      if(nx[i] >= 0 && nx[i] <= 100000 && !visited[nx[i]]){
        visited[cur] = true;
        queue.push([nx[i], time + 1]);
      }
    }
  }
}

bfs(N,K)

- 이번엔 nx 라는 배열에 이동한 값들을 모으고, 범위 설정을 바꾸었다. vscode와 백준 모두 정답이 되었다.

 

3. 정리

- if문을 어떤 방식으로 걸어주는가에 따라 결과가 달라질 수 있다는 생각을 했다. 

백준의 질문하기에 있는 반례들을 넣어 실행시켰을 때, 1차 풀이는 모두 통과를 했는데 어떤 이유 때문에 틀렸는지 정확하게는 모르겠다.

- 조건식을 걸 때 좀 더 확실한 방법으로 작성하는 편이 더 낫겠다 라는 생각을 했다.