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

문제 접근

문제를 읽어보면, 현재 위치에서 좌우로 한칸 이동하는데 1의 시간이 걸리고, *2의 위치로 순간이동하는데 시간이 소모되지 않는다. 시작점 N이 주어지고, 도착 목적지 K가 주어진다.
선분 혹은 이차원 맵에서 특정 위치에서 다른 종착점까지 이동하는데 걸리는 최솟값을 구하는 문제는 전형적인 bfs문제다.

잘 생각해보자.

1. N에서 N-1로 이동하는데 N까지 이동하는데 걸린 최소시간+1보다 빨리 움직일 수 있는가? -> 없다.
2. N에서 N+1로 이동하는데 N까지 이동하는데 걸린 최소시간+1보다 빨리 움직일 수 있는가? -> 없다.
3. N에서 N*2로 이동하는데 N까지 이동하는데 걸린 최소시간+0시간보다 빨리 움직일 수 있는가? -> 없다.

단, 위에서 2번과 3번 조건식은 잘 봐야한다. 이거 때문에 한 번 틀렸음.
N이 1인 경우는 2번 조건식이 거짓이 될 수 있다. 1에서 2로 이동하는데 +1이 아니라 *2로 이동하면 시간이 소모되지 않기 때문이다.

때문에, bfs 큐에 넣어줄때, 조건식을 *2 순간이동 먼저 위로 올려줘야 한다. 처음에 조건식 세 개 중 맨 마지막에 넣었다가 틀렸었다.

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[] map = new int[10_0001];
    static boolean[] isVisited = new boolean[10_0001];


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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Arrays.fill(map, 0);

        LinkedList<Integer> q = new LinkedList<>();
        q.add(N);
        map[N] = 0;
        isVisited[N] = true;

        while (!q.isEmpty()) {
            int curPosition = q.poll();
            if (curPosition == K) break;

            if (isIn(curPosition * 2) && !isVisited[curPosition * 2]) {
                map[curPosition * 2] = map[curPosition];
                q.add(curPosition * 2);
                isVisited[curPosition * 2] = true;
            }
            if (isIn(curPosition - 1) && !isVisited[curPosition - 1]) {
                map[curPosition - 1] = map[curPosition] + 1;
                q.add(curPosition - 1);
                isVisited[curPosition - 1] = true;
            }
            if (isIn(curPosition + 1) && !isVisited[curPosition + 1]) {
                map[curPosition + 1] = map[curPosition] + 1;
                q.add(curPosition + 1);
                isVisited[curPosition + 1] = true;
            }
        }

        System.out.println(map[K]);
    }

    static boolean isIn(int p) {
        return p >= 0 && p <= 10_0000;
    }
}