백준 13549번 숨바꼭질 3 JAVA

링크텍스트

설명

백준 1697번 숨바꼭질 문제는 코드에서 조금만 수정하면 쉽게 풀 수 있었다. 중요한 점은 순간이동을 사용할 때 시간이 늘어나지 않기 때문에 큐의 가장 처음에 넣어야 한다는 것이다. *2를 먼저 처리하는 이유는 순간이동이 다른 이동 방식보다 우선적으로 고려되어야 하기 때문에 시간을 최소화하려면 큐에서 가장 먼저 처리되도록 해야 했다. 다익스트라로 풀 수도 있다.

코드

import java.util.*;
import java.io.*;

class Main {
        static int n,k;
        static boolean [] check;
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        check =new boolean[100001];

        System.out.println(bfs(n));
        
    }

    public static int bfs(int start){
        Queue<int []> q = new LinkedList<>();
        q.offer(new int[]{start,0});

        check[start] = true;

        while (!q.isEmpty()) {
            int [] current = q.poll();

            int pos = current[0];
            int sec = current[1];

            if(pos==k) return sec;

            int [] nextPos = new int[] {pos*2,pos-1,pos+1};

            for(int i=0;i<nextPos.length;i++){
                int next = nextPos[i];

                if(next>=0 && next<=100000 && !check[next]){
                    check[next] = true;
                    
                    if (i == 0) {
                        q.offer(new int[] {next, sec});
                    } else {
                        q.offer(new int[] {next, sec + 1});
                    }
                }
            }
        }
        return -1;
    }
}

참고 글

https://velog.io/@silver_star/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-BFS