[Baekjoon] 1697번 : 숨바꼭질

1. 문제

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

• BFS 문제

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

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

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

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

// 예제 입력 1
5 17

// 예제 출력 1
4

2. 핵심 아이디어

• 특정 위치까지 이동하는 최단 시간을 계산
• 이동 시간이 모두 1초로 동일하므로, 간단히 BFS를 이용하여 해결할 수 있음
• 큐 구현을 위해 collections 라이브러리의 deque 이용

3. Python 문제풀이

import sys
from collections import deque
input = sys.stdin.readline

MAX = 100001
n, k = map(int, input().split())
arr = [0] * MAX

def bfs() :
  q = deque([n])
  while q :
    pos = q.popleft()
    if pos == k :
      return arr[pos]
    for next_pos in (pos - 1, pos + 1, pos * 2) :
      if 0 <= next_pos < MAX and not arr[next_pos] :
        arr[next_pos] = arr[pos] + 1
        q.append(next_pos)

print(bfs())

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Main {
  static int n;
  static int k;
  static int MAX = 100001;
  static int arr[] = new int[MAX];

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String input = br.readLine();
    String[] inputs = input.split(" ");

    n = Integer.valueOf(inputs[0]);
    k = Integer.valueOf(inputs[1]);

    int result = bfs(n);
    System.out.println(result);
  }

  private static int bfs(int node) {
    Queue<Integer> q = new LinkedList<Integer>();

    q.add(node);
    int index = node;
    int pos = 0;
    arr[index] = 1;
    while(!q.isEmpty()) {
      pos = q.remove();
      if (pos == k) {
        return arr[pos] - 1;
      }
      if (pos - 1 >= 0 && arr[pos - 1] == 0) {
        arr[pos - 1] = arr[pos] + 1;
        q.add(pos - 1);
      }
      if (pos + 1 <= MAX - 1 && arr[pos + 1] == 0) {
        arr[pos + 1] = arr[pos] + 1;
        q.add(pos + 1);
      }
      if (2 * pos <= MAX - 1 && arr[2 * pos] == 0) {
        arr[2 * pos] = arr[pos] + 1;
        q.add(2 * pos);
      }
    }
    return -1;
  }
}