[백준/java] 13549. 숨바꼭질 3, 0-1 BFS

문제보기

문제

위치 N에서 K까지 가는 최단 시간을 구하라 (0 <= N, K 정수 <= 10^5)
이동 방법은 3가지이다.
현재 위치가 X일때,
1. 0초 : X*2
2. 1초 : X-1
3. 2초 : X+1

문제 풀이 1 (BFS)

최단 시간을 구하기 때문에에 최단 경로라 생각해 바로 bfs 풀이를 하였다.
하지만, 틀렸다. 그 이유는 방문처리가 끝난 지점의 시간이 최단 시간이 아닐 수 있기 때문이다.

private static void check(int location,int time) {
        if(!visited[location]){
            queue.offer(new int[]{location, time});
            visited[location] = true;
            mintimes[location] = time;
        }
        else if(mintimes[location] > time){
            mintimes[location] = time;
        }
    }

따라서, 방문처리된 위치도 비교를 통해 최소 시간으로 갱신이 필요했다.

전체 코드

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

public class Main {
    static boolean[] visited = new boolean[100001];
    static int[] mintimes = new int[100001]; // idx : 위치, mintimes[idx] : idx 위치의 최소타임
    static Queue<int[]> queue = new LinkedList<>();
    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());

        int ans = bfs(N,K);
        System.out.println(ans);
    }

    private static int bfs(int N, int K) {

        queue.add(new int[]{N, 0});
        visited[N] = true;

        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int location = current[0];
            int time = current[1];
            if(location*2 <= 100000) {
                check(location*2, time);
            }
            if( location - 1 >= 0) {
                check(location-1, time+1);
            }
            if( location + 1 <= 100000){
                check(location+1, time+1);
            }
        }
        return mintimes[K];
    }

    private static void check(int location,int time) {
        if(!visited[location]){
            queue.offer(new int[]{location, time});
            visited[location] = true;
            mintimes[location] = time;
        }
        else if(mintimes[location] > time){ // 최소 시간 갱신
            mintimes[location] = time;
        }
    }
}

문제 풀이 2 (0-1 BFS)

해당 문제 풀이에는 시간 가중치가 0 또는 1이다.
이처럼 가중치가 0,1만 있는 그래프에서는 0-1 BFS 풀이가 효율적이라 한다.

✅ 0-1 BFS란?

양방향 큐인 덱(Deque)을 이용해서 가중치가 0인 간선은 앞쪽에 삽입, 간선이 1인 간선은 뒤쪽에 삽입함으로써 일반 BFS보다 더 빠르게 최단 거리를 구하는 특수한 BFS이다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean[] visited = new boolean[100001];
    static int[] mintimes = new int[100001]; //  mintimes[idx] : idx 위치의 최소타임
    static Deque<Integer> deque = new ArrayDeque<>();
    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());

        int ans = bfsdeque(N,K);
        System.out.println(ans);
    }

    private static int bfsdeque(int N, int K) {
        deque.addFirst(N);
        visited[N] = true;
        mintimes[N] = 0;

        while(!deque.isEmpty()){
            int location = deque.pollFirst();
            int time = mintimes[location];

            if(location*2 <= 100000 ) {
                check(location*2, time,0);
            }
            if( location - 1 >= 0) {
                check(location-1, time+1,1);
            }
            if( location + 1 <= 100000){
                check(location+1, time+1,1);
            }
        }
        return mintimes[K];
    }

    private static void check(int location,int time,int weight) { // weight : 가중치
        if(!visited[location]){
            if(weight==0) deque.addFirst(location); // 가중치가 0일 경우, 덱 앞에 삽입
            else deque.addLast(location); // 가중치가 1일 경우, 덱 뒤에 삽입
            visited[location] = true;
            mintimes[location] = time;
        }
        else if(mintimes[location] > time){ // 최소 시간 갱신
            mintimes[location] = time;
        }
    }
}

시간복잡도

한 위치는 한번만 방문하기 때문에 O(N)이다.