66 삐약 : 백준 13549| 숨바꼭질3 [바킹독 문제 풀이|BFS|JAVA]

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

 

package BKD_0x9_BFS;

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

public class BOJ_13549 {
    static int[] visited = new int[100001];

    static int min =Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        bfs(N,K);

        System.out.println(min);
    }
    static void bfs(int N, int K){


        Queue<Location> q = new LinkedList<>();
        q.offer(new Location(N,0));
        visited[N]=1;
        int[] d = {2,1,-1};


        while (!q.isEmpty()){
            Location l = q.poll();
            if(l.x==K) {
                min = Math.min(l.time, min);
            }
            if(l.x*2<=100000 && visited[l.x*2]==0){
                q.offer(new Location(l.x*2, l.time));
                visited[l.x*2] = 1;
            }

            if(l.x-1>=0 && visited[l.x-1]==0){
                q.offer(new Location(l.x-1, l.time + 1));
                visited[l.x-1] = 1;
            }

            if(l.x+1<=100000 && visited[l.x+1]==0){
                q.offer(new Location(l.x+1, l.time + 1));
                visited[l.x+1] = 1;
            }

        }
    }
    static boolean checkBoundary(int x){
        if(x>=0 && x<=100000 && visited[x]==0) return true;
        return false;
    }


    static class Location{
        int x;
        int time;
        public Location(int x, int time){
            this.x = x;
            this.time = time;
        }
    }
}

 

 

처음에는 다른 bfs 푸는것처럼 먼저 방문을 했으면 그걸로 땡

하고 생각을 했는데 

그렇게 진행하면 아니되었었땨...

 

순간이동을 하는 시간은 측정되지 않기 때문에 변수가 생길 가능성이 존재한다.

 

때문에 타겟 값까지 걸리는 시간이 최소일 경우를 판단해야 한다.

 

			if(l.x==K) {
                min = Math.min(l.time, min);
            }

 

뿅