[백준 13549] 숨바꼭질 3 - JAVA

 

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

 

0-1 bfs

 

일반 BFS에 정렬 기준이 없는 큐를 사용하고, 가중치 1인 탐색을 먼저 넣고 0을 이후 넣는 코드를 작성했다면

다음 탐색에서 둘 다 정답일 때, 최단거리가 아닌 오답(가중치 1이 더해진 값)이 출력될 수 있다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    int[] vst = new int[200001];
    Arrays.fill(vst, 200001);

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int ST = Integer.parseInt(st.nextToken());
    int ED = Integer.parseInt(st.nextToken());

    Deque<int[]> q = new ArrayDeque<>();
    vst[ST] = 0;
    q.offer(new int[]{ST, 0});

    while (!q.isEmpty()) {
      int[] cur = q.poll();
      int n = cur[0];
      int v = cur[1];

      if (n == ED) {
        System.out.println(v);
        return;
      }

      if (n > 0 && vst[n - 1] > v + 1) {
        vst[n - 1] = v + 1;
        q.offerLast(new int[]{n - 1, v + 1});
      }

      if (n < 200000 && vst[n + 1] > v + 1) {
        vst[n + 1] = v + 1;
        q.offerLast(new int[]{n + 1, v + 1});
      }

      if (n <= 100000 && vst[n * 2] > v) {
        vst[n * 2] = v;
        q.offerFirst(new int[]{n * 2, v});
      }
    }
  }
}