[Java] 백준 1697번 숨바꼭질

이 글은 백준 1697번 숨바꼭질을 풀이한다. 코드는 Java로 구현하였다.

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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초
• 메모리: 128MB

풀이

접근

이 문제는 BFS 알고리즘으로 1차원 배열을 사용해서 해결했다.

예제 입력인 '5 17'을 기준으로 설명한다.

먼저, 걸린 시간을 저장하는 1차원 배열을 하나 생성해 준다. 이때, 배열의 값은 -1로 초기화시켜주어야 한다.

 

수빈이의 초기 위치가 5이기 때문에 배열의 다섯번째 인덱스 값을 0으로 변경해 준다.

그러고 나서 (X-1, X+1, X*2)의 이동범위를 주면서 BFS를 돌려준다.

그리고 동생 위치인 17번째 인덱스 값이 -1에서 다른 값으로 바뀌었을 때 BFS를 종료하고 해당 값을 출력시켜 주면 답을 구할 수 있다.

 

아래 그림에서는 설명을 쉽게 하기 위해 0~19번째 인덱스 값만 잡아둔 것이다.

실제 배열의 공간 크기는 100,000이다.

BFS 돌리기 전

BFS 돌린 후

문제를 보면 수빈이가 이동 중에 반드시 0에서 100,000 사이에만 있어야 한다는 조건은 없다.

예를 들어, 100,000 밖으로 나갔다가 다시 안으로 올 수도 있다고 생각할 수도 있는데,

이 문제에서는 가장 빠른 경로를 찾는 문제이기 때문에 100,000을 탈출하는 상황이 나올 수가 없게 된다.

 

이 문제에서는 운 좋게 논리적으로 생각을 했을 때 수빈이가 문제에서 주어진 범위 내에서만 움직이게 되었지만 다른 문제에서는 아닐 수도 있기 때문에 항상 이런 것도 생각해 보면서 풀도록 해야겠다.

구현

코드

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

public class baekjoon1697 {

  static int[] dist;
  static int[] moves;
  static Queue<Integer> Q;
  static int MAX_SIZE = 100_001;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    dist = new int[MAX_SIZE]; // 수빈이와 동생이 이동하거나 서있을 수 있는 자리
    Q = new LinkedList<>();
    // 배열 초기화
    Arrays.fill(dist, -1); // 배열 -1로 초기화
    Q.offer(N);
    dist[N] = 0;
    // 시작
    while (dist[K] == -1) {
      int cur = Q.poll();
      moves = new int[] { cur + 1, cur - 1, cur * 2 }; // 수빈이가 이동할 수 있는 거리

      for (int move : moves) {
        if (move < 0 || move >= MAX_SIZE) continue; // 범위 체크
        if (dist[move] != -1) continue; // 방문 체크
        dist[move] = dist[cur] + 1;
        Q.offer(move);
      }
    }
    System.out.println(dist[K]);
  }
}