[baekjoon] 1697 숨바꼭질 (Javascript,C++)

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

---

접근 : BFS

 

Javascript

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let dn = [1, -1, 2];

class Queue {
  constructor() {
    this.arr = [];
    this.head = 0;
    this.tail = 0;
  }

  push(data) {
    this.arr[this.tail++] = data;
  }
  pop() {
    return this.arr[this.head++];
  }
  size() {
    return this.tail - this.head;
  }
}

let [n, k] = input[0].split(" ").map((v) => +v);
function solution() {
  if (n == 0 && k == 0) {
    console.log(0);
    return 0;
  }
  let visited = new Array(2000002).fill(-1);

  let q = new Queue();
  q.push(n);
  visited[n] = 0;

  while (visited[k] == -1) {
    let cur = q.pop();
    for (let dir = 0; dir < 3; dir++) {
      let dx;
      if (dir == 2) {
        dx = cur * dn[dir];
      } else {
        dx = cur + dn[dir];
      }

      if (dx < 0 || dx > 100000) continue;
      if (visited[dx] >= 0) continue;
      visited[dx] = visited[cur] + 1;
      q.push(dx);
    }
  }

  console.log(visited[k]);
}

solution();

---

C++

#include <bits/stdc++.h>
using namespace std;
int n,k;
int visited[200002];

int dn[3]={1,-1,2};


int main()
{
  freopen("input.txt", "r", stdin); //제출 시 삭제

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

  cin>>n>>k;

  if(n==0&&k==0) {cout<<0<<"\n"; return 0;}
  fill(visited,visited+200002,-1);
  
  queue<int> q;
  q.push(n);
  visited[n]=0;

  while(visited[k]==-1){
    int cur = q.front();
    q.pop();
    for(int dir=0;dir<3;dir++){
      int dx;
      if(dir==2){
        dx = cur * dn[dir];
      } else{
        dx = cur + dn[dir];
      }

      if(dx<0||dx>100000) continue;
      if(visited[dx]>=0) continue;
      visited[dx] = visited[cur]+1;
      q.push(dx);
    }
  }

  cout<<visited[k]<<"\n";


  return 0;


}