[JS] 백준 13549번 : 숨바꼭질 3 - 그래프이론, BFS, 너비우선탐색, 덱 자료구조(Double Ended Queue)

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

13549번: 숨바꼭질 3

 

 

 

📋풀이방법

1. BFS를 이용한다

2. visited라는 100100정도 크기의 배열을 선언해서 0으로 초기화해준다

 -이 배열은 걷기와 순간이동을 할 때 같은 곳을 방문하지 않도록하기 위한 배열임

3. queue에 시작점 N과 시간초 cnt를 넣어주고 visited[N]=1로 방문표시를 해준다.

4. queue에서 하나씩 빼면서 N이 K가 되면 반복을 종료해준다.

5. K가 아니면 N을 [+1,-1.*2]를 해주고, 그 값이 visited에서 방문을 했는지 확인한다.

6. 방문하지 않았으면 방문표시를 해주고, 그 경로를 queue에 push한다.

 -이때 순간이동은 시간초가 증가하지 않으므로 우선적으로 BFS를 탐색해야한다. 

 -그러므로 순간이동인 *2 값은 queue에 unshift를 해줌으로써 우선적으로 탐색하게 된다.

 -걷기를 하는 +1과 -1은 push로 해준다.

7. ☝중요한점은 만약 N이  [+1,-1.*2] 값이 0보다 작아지거나 

 - 문제에서 주어진 100000보다 커지면 그 값들은 필요가 없으므로 탐색에서 빼줘야한다.

 

 

내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, K] = input[0].split(" ").map(Number);
const visited = Array.from({ length: 100100 }, () => 0);
let queue = [];

queue.push([N, 0]);
visited[N] = 1;
let result = 0;
while (queue.length) {
  let [n, cnt] = queue.shift();

  if (n == K) {
    result = cnt;
    break;
  }
  for (next of [n * 2, n - 1, n + 1]) {
    if (!visited[next] && next >= 0 && next <= 100000) {
      visited[next] = 1;
      if (next == n * 2) {
        queue.unshift([next, cnt]);
      } else {
        queue.push([next, cnt + 1]); 
      }
    }
  }
}
console.log(result);

 

 

💢어려웠던 점

1. 처음에 순수 BFS로 풀었더니 시간초과가 났다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, K] = input[0].split(" ").map(Number);

let queue = [];

queue.push([N, 0]);
let result = 0;
while (queue.length) {
  let [n, cnt] = queue.shift();

  if (n == K) {
    result = cnt;
    break;
  }

  let a = [n + 1, cnt + 1];
  let b = [n - 1, cnt + 1];
  let c = [2 * n, cnt];

  queue.push(a);
  queue.push(b);
  queue.push(c);
}
console.log(result);

2. 그래서 DP라는 배열을 이용해서 이동하는 값들을 기록하면서 cnt가 현재 기록된 값보다 작을 때만 queue에 값을 넣는 것을 진행했다.

- 하지만 시간초과가 났다.

- 이 방법은 잘못된 방법이였다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, K] = input[0].split(" ").map(Number);

let queue = [];
let dp = Array.from({ length: K + 1 }, () => 100000);

queue.push([N, 0]);
let result = 0;
while (queue.length) {
  let [n, cnt] = queue.shift();
  if (dp[n] < cnt) {
    continue;
  } else {
    dp[n] = cnt;
  }

  if (n == K) {
    result = cnt;
    break;
  }

  let a = [n + 1, cnt + 1];
  let b = [n - 1, cnt + 1];
  let c = [2 * n, cnt];

  queue.push(a);
  queue.push(b);
  queue.push(c);
}
console.log(result);

-현재 이 코드의 로그를 찍으면 왼쪽 이미지와 같이 나온다.

-원래 올바른 알고리즘은 오른쪽 이미지와 같이 출력되어야한다.

왼쪽 잘못된 코드, 오른쪽 잘 된 코드

-문제를 보면 방문이 아닌 cnt값으로 선별하기 때문에 똑같은 곳을 계속해서 가져오는 것이다.

-예를 들어 현재 1 -> 50으로 가는 방법의 로그를 찍은 것이다.

-[1,0] 부터 시작한다.

-그럼 다음은 [2, 0], [2, 0] [0,1] 을 검사한다. -> 1*2, 1+1, 1-1 이다.

-근데 잘못된 코드는[2,0]을 queue에 두번 넣는다. 

-잘 된 코드는 [2,0]은 방문한 좌표니까 queue에 넣지 않은 모습이다.

- 이를 통해 값으로 하게되면 위와 같이 같은 값을 계속 queue에 넣어서 무한반복이 생기게되는 것이다.

- 이 이유말고도 다른 이유가 있는데 아직 생각해내지 못했다. 아무튼 값으로 하는 방법은 잘못된 방법인 것 같다.