백준 12851번 - 숨바꼭질 2

문제

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

리뷰

이전에 숨바꼭질 시리즈 문제를 0-1 BFS 로직을 이용하여 풀이해본 적 있기에
비슷한 관점으로 접근하였다. 다만, K에 도달하였을 경우의 수를 카운팅해야
하기에 K는 방문 표시를 하지 않고 넘어가야 하므로 탐색 과정에서 방문 표시를
Queue에서 poll 연산을 수행할 시 하는 발상을 떠올리는 데 시간이 좀 필요했던
것 같다.

전체 로직의 시간 복잡도는 최악의 경우 $O(N+K)$ 로 수렴하며 문제에서 주어진
값의 범위에서 최대값을 고려해도 시간 제한을 무난히 통과한다.
다른 숨바꼭질 시리즈 문제를 풀이해봤으면 처음 접근은 어렵지 않은
문제였던 것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

import static java.lang.Integer.*;

public class Main {

    static final int MAX=100_001; // 탐색 범우
    static int N, K;
    static List<Integer> list = new ArrayList<>(); //K 도달 가능 경우 저장 리스트
    static int minDist=MAX_VALUE; // K 도달 가능 최단 거리
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N= parseInt(st.nextToken());
        K= parseInt(st.nextToken());

        visited=new boolean[MAX];

        bfs(N);

        // 최단 거리로 K를 도달하는 경우만 filter
        List<Integer> result = list.stream()
                .filter(num -> num == minDist)
                .collect(Collectors.toList());

        System.out.println(minDist);
        System.out.println(result.size());
        br.close();
    }

    static void bfs(int start){
        ArrayDeque<Node> deque = new ArrayDeque<>();
        deque.offerLast(new Node(start, 0));
        visited[start]=true;

        while(!deque.isEmpty()){
            Node current=deque.poll();

            /**
             * K를 도달한 경우, list에 거리를 더해주고
             * 최단 거리를 갱신해준다.
             */

            if(current.num==K){
                list.add(current.level);
                minDist=Math.min(minDist, current.level);
                continue;
            }

            visited[current.num]=true;

            enqueueOperation(current.num-1, current.level, deque, false);
            enqueueOperation(current.num+1, current.level, deque, false);
            enqueueOperation(2*current.num, current.level, deque, true);
        }
    }

    /**
     * Deque에 BFS를 최적으로 진행할 수 있도록 enqueue 연산을 수행하는 메서드
     * @param index
     * @param level
     * @param deque
     * @param isTwice
     */
    static void enqueueOperation(int index, int level, ArrayDeque<Node> deque, boolean isTwice){
        if(validIndex(index)){
           if(!visited[index]){
               if(isTwice) //거리를 2배씩 건너뛰는 경우, 가장 먼저 poll 될 수 있게 넣어준다.
                   deque.offerLast(new Node(index, level+1));
               else
                   deque.offer(new Node(index, level+1));
           }
        }
    }

    static boolean validIndex(int index){
        return 0<=index && index<=100_000;
    }

    static class Node{
        int num, level;

        public Node(int num, int level) {
            this.num = num;
            this.level = level;
        }
    }
}

결과