이번에 풀어본 문제는
백준 13549번 숨바꼭질 3 입니다.

📕 문제 링크

❗️코드

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

class Play
{
    int x,time;

    public Play(int x, int time)
    {
        this.x = x;
        this.time = time;
    }
}
public class Main{
    static int N,K;
    static int [] min;
    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());
        if(K <= N)
        {
            System.out.print(N-K);
            return;
        }
        min = new int[(K*2)+1];
        Arrays.fill(min,Integer.MAX_VALUE);
        PriorityQueue<Play> pq = new PriorityQueue<>(new Comparator<Play>()
        {
            @Override
            public int compare(Play o1, Play o2)
            {
                return o1.time - o2.time;
            }
        });

        pq.add(new Play(N,0));

        int answer = 0;
        while(!pq.isEmpty())
        {
            Play cur = pq.poll();
            if(cur.x == K)
            {
                answer = cur.time;
                break;
            }
            for(int idx = 0; idx < 3; ++idx)
            {
                int mx = move(cur.x,idx);
                if(!isValid(mx)) continue;
                int tmpTime = 1;
                //순간이동일때는 0초소요
                if(idx == 2) tmpTime--;
                int totalTime = cur.time+tmpTime;
                if(min[mx] > totalTime)
                {
                    min[mx] = totalTime;
                    pq.add(new Play(mx,totalTime));
                }
            }
        }
        System.out.print(answer);
    }
    static int move(int x, int action)
    {
        //action(0=앞으로,1=뒤로,2=순간이동)
        if(action == 0) return x+1;
        else if(action == 1) return x-1;
        else return x*2;
    }
    static boolean isValid(int x)
    {
        return x >= 0 && x <= (K*2);
    }
}

📝 풀이

수빈이와 동생이 숨바꼭질을 합니다. 수빈이는 최단시간 내에 동생을 잡아야 하고, 동생은 K위치에 멈춰있으며, 수빈이는 N의 위치에서 출발합니다. 수빈이가 할 수 있는 동작은 앞으로1칸, 뒤로1칸, 현재위치2로의 순간이동입니다. 매 이동에는 1초가 소요되며, 순간이동은 시간을 소모하지 않습니다. 3가지 이동을 활용하여 동생을 잡을 수 있는 최단시간을 구하는 문제입니다.
저는 우선순위큐를 활용해보았습니다. 처음에는 우선순위큐를 사용하면 비용이 들지않는 곱하기 동작을 무의미하게 반복할 것 같아서, 사용하지 않으려고 했었는데, 범위가 엄청 크지도 않고 K2만큼의 배열로 크기를 맞춰주면, 그렇게 소모가 클 것 같지는 않아서 그대로 채용했습니다. 예외로, K값이 N보다 작거나 같을 경우가 있는데, 어차피 K가 N보다 작다면 뒤로 -1칸 이동하는 경우를 반복하는 것이 최단 시간이기 때문에, 해당 경우에는 N-K를 출력해주고 함수를 종료하면 됩니다.
또한 반복되는 이동을 방지하기 위해 해당 칸에 도착했던 최단 시간을 담아두는 min배열을 만들었습니다. mx칸으로 이동을 시도할때, min[mx]값을 체크하여 이전에 더 짧은 시간으로 해당 칸에 도달한 적이 있다면, 해당 칸으로는 더 이상 이동할 필요가 없기 때문에 다음 반복으로 넘겨줄 수 있습니다.
위와 같은 방식으로 탐색을 진행하면, K를 가장 먼저 마주친 반복이 최솟값이 되기 때문에, 바로 시간을 출력해주면 됩니다.

📜 후기

K가 N보다 작은 경우를 생각하지 못해 잠시 헤맸습니다 ㅋㅋㅋ