숨바꼭질(백준 코딩테스트 1697번, BFS, NodeJS 풀이)

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

 

 

문제 수준:

실버1

 

 

문제 요약:

0~100000만큼의 너비가 있는 도로 위에서 수빈이와 동생은 숨바꼭질을 하고있다...

수빈이가 가능한 이동 방식은

    1. 앞으로 한 칸

    2. 뒤로 한 칸

    3. 두 배 점프

이 있다.

이 모든 행동은 1초의 시간을 소요한다.

그렇다면, 동생의 위치까지 수빈이가 최단 시간으로 도달하려면 몇 초가 걸리는가?

 

 

입출력 예 (입력 / 출력):

첫 줄에 수빈이의 위치와 동생을 위치가 주어진다.

최단시간으로 동생을 잡는다면 몇 소가 걸리는지 출력하라.

 

 

문제 풀이 전략:

계단오르기 문제와 조금 비슷한 유형이다. BFS입문 문제로 유명한듯 하다.

푸

 

1. queue에 수빈이의 위치를 넣는다.

2. queue에서 위치 하나를 꺼내서(k라고 하자), 방문처리를 한다.

3. k에서 접근할 수 있는 다른 위치들을 queue다시 넣는다.

 

원래 방문처리를 0혹은 1 정도의 값으로 하는 경우가 있는데, '전 회차 방문처리 + 1'을 방문처리 값으로 해주면 카운터(cnt)의 역할도 할  수 있다.

 

이렇게 할 시 방문처리 배열은 아래처럼 시작점을 0으로 했을 시 각각의 노드가 얼마나 멀리 떨어져 있는지 볼 수 있게 된다.

[5, 4, 3, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, ...]

 

 

내 풀이:

class Queue { // 큐를 선언 (자바스크립트는 내장 큐가 없다.)
  constructor() {
    this.list = {};
    this.tail = 0;
    this.head = 0;
  }
  enqueue(item) {
    this.list[this.tail] = item;
    this.tail++;
  }
  dequeue() {
    const temp = this.list[this.head];
    delete this.list[this.head];
    this.head++;
    return temp;
  }
  getLength() {
    return this.tail - this.head;
  }
}

const fs = require("fs").readFileSync("dev/stdin");
const [start, goal] = fs.toString().trim().split(" ").map(Number);

const visited = new Array(100001).fill().map((x) => 0); //그래프 및 방문처리를 해줄 그래프

function bfs() {
  const queue = new Queue(); // queue생성
  queue.enqueue(start); // 처음 노드를 넣는다.
  while (queue.length !== 0) { // queue가 빌때까지 반복
    let cur = queue.dequeue(); // 하나 뽑아서
    if (cur === goal) return visited[cur]; // 목표인지 확인하여 맞다면 방문노드에 적힌 값을 표출.
    for (let nxt of [cur + 1, cur - 1, cur * 2]) { // 이동할 수 있는 범위에 접근
      if (nxt < 0 || nxt > 100001) continue; // 범위를 벗어나면 continue로 다음 진행
      if (!visited[nxt]) { // 방문을 아직 안 한 곳이라면
        queue.enqueue(nxt); // queue에 추가함
        visited[nxt] = visited[cur] + 1; // 전의 node 값 + 1로 지정
      }
    }
  }
}
console.log(bfs());

 

대강 BFS 푸는 꼴을 이젠 기억하기 때문에 매우 빠르게 풀 수 있을 줄 알았는데 메모리 초과로 고생하였다.

0 미만의 수거나 100000 초과하는 수까지 탐색하는 것을 멈추기 위해 예외처리를 성실히 해주면 메모리 초과를 해결할 수 있다.