[boj/java]13549 숨바꼭질3

acmicpc.net/problem/13549

엄청 쉽다고 생각했는데 막상 풀려니 또 안풀리던 문제^^
0-1 bfs는 가중치가 0과 1이 있는 그래프에서 최단거리를 구할 때 사용하는 알고리즘이다. 처음에는 0-1 bfs가 뭔지도 몰라서 걍 bfs겠거니 하고 풀었는데 아니었다.

일단 우선순위가 있기 때문에 우선순위 큐를 사용하거나,
가중치가 0인 경우를 큐에 먼저 삽입해주고, 가중치가 1인 경우를 나중에 삽입해줘야한다.
찾아보니까 디큐를 사용해서 뒤에다가 넣어줘야 한다는데,
어차피 이 경우에는 pos*2인 경우를 먼저 넣고, pos+1과 pos-1을 나중에 넣어주면 디큐의 형태처럼 쓸 수 있기 때문에 그냥 순서대로 큐에 넣어줬다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int[] dx = {-1, 1};

    static int solution(int start, int destination) {
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[100001];
        q.add(new int[]{start, 0});
        visited[start] = true;

        while (!q.isEmpty()) {
            int[] p = q.poll();
            int pos = p[0];
            int move = p[1];

            if (pos == destination) {
                return move;
            }

            int jump = pos * 2;
            if (jump < 100001 && !visited[jump]) {
                visited[jump] = true;
                q.add(new int[]{jump, move});
            }

            for (int i = 0; i < 2; i++) {
                int next = pos + dx[i];
                if (next >= 0 && next < 100001 && !visited[next]) {
                    visited[next] = true;
                    q.add(new int[]{next, move + 1});
                }
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        int N;
        int K;

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        System.out.println(solution(N, K));
    }
}

참고 : https://loosie.tistory.com/243