[백준] 13549번 숨바꼭질 3

1) 생각

너무 편안하게 문제그대로만 보았기 때문에 왜 틀린지를 몰라서 시간을 많이 잡아 먹었다.

순간이동의 경우 시간을 0초 소비하기 때문에 한 번에 갈 수 있다면 제일 빠른 경로이다.

문제에 나와있는 순서대로 왼쪽, 오른쪽, 두 배 순서대로 BFS를 돌리게되면 n=1, k=2 란 반례가 존재하게된다.

2) 방안

n=1, k=2일 경우 순서대로 왼쪽, 오른쪽, 두 배를 하면 두배가 되기전에 반복문을 종료하므로 두배를 먼져 체크해주는 것으로 해결하였다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main{
    static int n,k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        visited = new boolean[100002];
        min = Integer.MAX_VALUE;
        solve();
        System.out.println(min);
    }
    
    static boolean[] visited;
    static int min;
    private static void solve() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(n,0));
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            if(t.n==k) {
                min = Math.min(min, t.time);
                break;
            }
            if(visited[t.n]) continue;
            visited[t.n] = true;
            // 1) x-1로 이동
            if(t.n-1>=0) 
                if(!visited[t.n-1]) queue.add(new Pair(t.n-1,t.time+1));
            // 3) x*2로 이동
            if(t.n*2<=100000)
                if(!visited[t.n*2]) queue.add(new Pair(t.n*2,t.time));
            // 2) x+1로 이동
            if(t.n+1<=100000)
                if(!visited[t.n+1]) queue.add(new Pair(t.n+1,t.time+1));
        }
    }
    
    static class Pair{
        private int time = 0;
        private int n = 0;
        public Pair(int n,int time) {
            this.time = time;
            this.n = n;
        }        
    }
}