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

풀이 아이디어

q에 현재 좌표와 이동거리를 담은 객체 Position을 넣고
boolean[100_001] visited배열에 탐색여부를 저장해서
중복 탐색한 곳은 또 하지 않도록 했다.BFS를 사용해서 탐색

트러블 슈팅

49%에서 틀림

q.add(new Position(x*2, tick));
q.add(new Position(x-1, tick+1));
q.add(new Position(x+1, tick+1));

처음에 구현했을 때는 큐에 다음 탐색장소를 그냥 add로 넣어 무작위로 넣었었다.
하지만 이렇게 된 경우 문제 조건을 살펴보면
현재 위치가 x일 때 0초 뒤에 x*2로 순간이동을 할 수 있는데
위에서 if문 순서대로 넣으니까 첫 위치에서 순간이동을 여러번 해서 갈 수 있는
모든 장소는 0초만에 도착할 수 있는 걸로 되야하기 때문에
순간이동을 한 경우를 먼저 따져주도록 큐 맨 앞에 넣어야한다.
그래서 자료구조를 deque으로 바꿔 순간이동 시 덱의 맨 앞, 1초 이동은 덱의 맨 뒤로 가도록
위치 정보를 넣어줬다.

q.addFirst(new Position(x*2, tick));
q.addLast(new Position(x-1, tick+1));
q.addLast(new Position(x+1, tick+1));

99%에서 틀림

// 순간이동 하는 경우 
if(x*2<=100000 && !visited[x*2]){
    visited[x*2] = true;
    q.addFirst(new Position(x*2, tick));
}
// x+1하는 경우
if(x+1<=100000 && !visited[x+1]){
    visited[x+1] = true;
    q.addLast(new Position(x+1, tick+1));
}
// x-1하는 경우
if(x-1>=0 && !visited[x-1]){
    visited[x-1] = true;
    q.addLast(new Position(x-1, tick+1));
}

큐에 넣어주는 순서를 -1로 이동하는 경우가 +1로 이동하는 경우보다 먼저 오도록 바꿔줬다.
아무래도 if로 설정한 범위가 if(x-1>=0 && !visited[x-1])으로 줬기 때문인 것으로 보인다.

// 순간이동 하는 경우 
if(x*2<=100000 && !visited[x*2]){
    visited[x*2] = true;
    q.addFirst(new Position(x*2, tick));
}
// x-1하는 경우
if(x-1>=0 && !visited[x-1]){
    visited[x-1] = true;
    q.addLast(new Position(x-1, tick+1));
}
// x+1하는 경우
if(x+1<=100000 && !visited[x+1]){
    visited[x+1] = true;
    q.addLast(new Position(x+1, tick+1));
}

추가로 탐색하다가 목적지에 도착한 경우 최소 이동시간을 출력하고 반환하도록 수정했다.

// K에 도착하면 갱신 
if(x == K){
    System.out.println(tick);
    return;
}

풀이 코드

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

class _13549{
    static class Position{
        int x;
        int tick;
        Position(int x, int tick){
            this.x = x;
            this.tick = tick;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

       boolean[] visited = new boolean[100_001];
        Arrays.fill(visited, false);

        int minCount = Integer.MAX_VALUE;

        Deque<Position> q = new LinkedList<>();
        q.add(new Position(N, 0));
        visited[N] = true;
        int x, tick;

        while(!q.isEmpty()){
            // q에서 뽑아 현재 좌표를 확인한다. 
            Position current = q.poll();
            x = current.x;
            tick = current.tick;

            // K에 도착하면 갱신 
            if(x == K){
                // minCount = Math.min(minCount, tick);
                System.out.println(tick);
                return;
            }
            // 순간이동 하는 경우 
            if(x*2<=100000 && !visited[x*2]){
                visited[x*2] = true;
                q.addFirst(new Position(x*2, tick));
            }
            // x-1하는 경우
            if(x-1>=0 && !visited[x-1]){
                visited[x-1] = true;
                q.addLast(new Position(x-1, tick+1));
            }
            // x+1하는 경우
            if(x+1<=100000 && !visited[x+1]){
                visited[x+1] = true;
                q.addLast(new Position(x+1, tick+1));
            }
        }

        System.out.println(minCount);
    }
}