[G5] 숨바꼭질 3 : 13549 : Java - BFS

1. 💎 문제

13549번: 숨바꼭질 3

 

 

 

 

2.  🤔어떻게 풀까

처음 봤을 때는 누적하면 풀어야될 것 같아서 DP로 풀어야하나 생각했다. 하지만 보다보니깐 큐를 이용해서 <거리, 시간> 정보를 넣어서 관리해주면 될 것 같았다. 현재 위치에서 이동할 수 있는 경우의 수는 -1, +1, *2로 3가지이다. 그러므로 이 3가지 위치에 대해만 생각하면 되며, 현재 노드를 거쳐서 다음 위치를 갈 때 비용이 적은 경우 => 비용 갱신 및 큐에 추가 하기로 했다.

이 과정을 큐가 빌 때까지 반복하며, K위치에 다 다를 경우는 여러 경우의 수가 있으므로, `Math.min`을 이용하여 최소값을 `ans`로 하였다.

 

 

3. 📄 전체코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_숨바꼭질3 {

    static final int MAX = 100001;
    static BufferedReader br;
    static int N;
    static Queue<Data> que;
    static int ans =MAX;

    public static void main(String [] args) throws Exception{
        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());

        int [] times = new int[MAX];
        Arrays.fill(times, MAX);

        que = new LinkedList<>();
        que.add(new Data(N, 0));
        times[N] = 0;
        while(!que.isEmpty()){

            Data curData = que.poll();
            if(curData.pos == K){
                ans = Math.min(curData.time, ans);
            }

            // -1칸
            if(curData.pos >0 && times[curData.pos-1] > curData.time+1){
                times[curData.pos-1] = curData.time+1;
                que.add(new Data(curData.pos-1, curData.time +1));
            }

            // +1칸
            if(curData.pos <MAX-1 && times[curData.pos+1] > curData.time+1){
                times[curData.pos+1] = curData.time+1;
                que.add(new Data(curData.pos+1, curData.time +1));
            }

            // *2칸
            if(curData.pos*2 < MAX && times[curData.pos*2] > curData.time){
                times[curData.pos*2] = curData.time;
                que.add(new Data(curData.pos*2, curData.time));
            }
        }
        System.out.println(ans);
    }
}

class Data{
    int pos;
    int time;

    public Data(int pos, int time){
        this.pos = pos;
        this.time = time;
    }
}