BFS 문제풀이(1)

1. 숨바꼭질(1697)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

작성한 코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const MAX = 100001;
let [n, k] = input[0].split(" ").map(Number); // 초기 위치(N)와 동생의 위치(K)
let visited = new Array(MAX).fill(0); // 각 위치까지의 최단 시간

// 너비 우선 탐색(BFS)
function bfs() {
  queue = new Queue();
  queue.enqueue(n);
  // 큐가 빌 때까지 반복
  while (queue.getLength() != 0) {
    let cur = queue.dequeue();
    // 동생의 위치에 도달한 경우
    if (cur == k) {
      return visited[cur]; // 최단 시간 출력
    }
    for (let nxt of [cur - 1, cur + 1, cur * 2]) {
      // 공간을 벗어난 경우 무시
      if (nxt < 0 || nxt >= MAX) continue;
      // 아직 방문하지 않은 위치라면
      if (visited[nxt] == 0) {
        visited[nxt] = visited[cur] + 1;
        queue.enqueue(nxt);
      }
    }
  }
}
console.log(bfs());

풀이

• 초기 위치(N)에서 동생의 위치(M)에 도달하는 최단 시간을 계산하는 문제
• 모든 순간이동(간선)의 비용이 1초로 동일하므로, BFS로 최단 시간 계산 가능
• 초기 위치 5에서 동생의 위치 17까지 갈 수 있는 방법

2. 나이트의 이동(7562)

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

작성한 코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

dx = [-2, -2, -1, -1, 1, 1, 2, 2];
dy = [-1, 1, -2, 2, -2, 2, -1, 1];

let testCases = Number(input[0]); // 테스트 케이스의 수
let line = 1;
while (testCases--) {
  let l = Number(input[line]);
  let [x, y] = input[line + 1].split(" ").map(Number); // 현재 위치
  let [targetX, targetY] = input[line + 2].split(" ").map(Number); // 목표 위치
  let visited = []; // 방문 정보
  for (let i = 0; i < l; i++) visited.push(new Array(l).fill(0));
  queue = new Queue(); // 너비 우선 탐색 수행
  queue.enqueue([x, y]);
  visited[x][y] = 1;
  while (queue.getLength() != 0) {
    let cur = queue.dequeue();
    x = cur[0];
    y = cur[1];
    // 현재 위치에서 이동하고자 하는 위치 확인
    for (let i = 0; i < 8; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue; // 공간을 벗어난 경우 무시
      if (visited[nx][ny] == 0) {
        visited[nx][ny] = visited[x][y] + 1;
        queue.enqueue([nx, ny]);
      }
    }
  }
  line += 3; // 다음 테스트 케이스로 이동
  console.log(visited[targetX][targetY] - 1); // 항상 도달 가능
}

풀이

• 가중치가 없는 그래프에서의 최단 경로 구하는 문제 → BFS 사용
  • 나이트가 존재하는 위치에서 BFS를 수행하여 모든 칸까지의 최단 거리 계산
• 8가지 방향으로 이동 가능

  dx = [-2, -2, -1, -1, 1, 1, 2, 2];
  dy = [-1, 1, -2, 2, -2, 2, -1, 1];