[백준/1697] 숨바꼭질 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1697

• 분류 : BFS

• 풀이 시간 : 30분

문제 해설

1. 수빈이는 N에 위치, 동생은 K에 위치 (0 <= N, K <= 100000)
2. 수빈이는 1초 안에 N-1, N+1위치로 걸어서 이동하거나, 2*N위치로 순간이동할 수 있음
3. 수빈이가 K 위치까지 걷거나 뛰어서 가는데 최소 몇초 걸리나

Solution

풀이 접근 방법

1. N - 1, N + 1, N * 2 위치로 BFS

정답 코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.valueOf(st.nextToken());
    int K = Integer.valueOf(st.nextToken());

    if (N == K) {
      bw.write(0 + "\n");
    } else {
      bw.write(bfs(N, K) + "\n");
    }

    bw.flush();
    bw.close();

  }

  static boolean isIn(int n) {
    if (0 <= n && n <= 100000) {
      return true;
    }
    return false;
  }

  static int bfs(int N, int K) {
    int minCnt = 987654321;
    boolean[] visited = new boolean[100001];
    Queue<int[]> queue = new LinkedList<int[]>();

    // [위치, 해당 위치로 도착한 초]
    queue.add(new int[] { N, 0 });
    visited[N] = true;

    while (!queue.isEmpty()) {
      int[] arr = queue.poll();
      int n = arr[0];
      int cnt = arr[1];

      // 다음 위치를 담은 배열
      int[] next = new int[] { n - 1, n + 1, n * 2 };

      for (int i = 0; i < 3; i++) {
        // 다음 위치가 도착 위치면 최소 초 갱신
        if (next[i] == K) {
          minCnt = Math.min(minCnt, cnt + 1);
          continue;
        }

        // 범위 안을 벗어나거나 이미 방문한 공간(더 작은 초에 방문해서 다시 안봐도 됨)이면 생략
        if (!isIn(next[i]) || visited[next[i]])
          continue;

        visited[next[i]] = true;
        queue.add(new int[] { next[i], cnt + 1 });
      }
    }

    return minCnt;
  }

}