[백준] 1697 숨바꼭질 - Java

 

 

 

최소 시간을 구하라고 했으니.. bfs를 사용해 dist를 갱신하고 최소 시간을 출력하면 될 것 같다.

기존 문제는 격자 혹은 그래프를 대놓고 줘서 그래프를 어떻게 구성해야 할 지 쉽게 떠올릴 수 있었는데, 이번 문제에서는 그래프에 대한 단서가 별로 없다.

 

먼저 그래프를 디자인해보자.

 

정점은 술래가 위치한 상태 / 간선은 +1. -1. *2 세 가지로 구성할 수 있겠다.

 

 

위의 조건에 맞춰 그래프를 구성하고 bfs를 돌려 답을 구하자.

 

 

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

public class Main {

    static int N;    
    static int K;    
    
    static int[] dist;
    static boolean[] visit;
    

    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());

        dist = new int[200_000];
        visit = new boolean[200_000];

        bfs();
        System.out.println(dist[K]);
        
    }

    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        
        q.add(N);
        visit[N] = true;
        dist[N] = 0;

        while(!q.isEmpty()){
            int x = q.poll();

            if(x - 1 >= 0 && !visit[x-1]){
                visit[x-1] = true;
                dist[x-1] = dist[x] + 1;
                q.add(x-1);
            }

            if(x+1 <= 100_000 && !visit[x+1]){
                visit[x+1] = true;
                dist[x+1] = dist[x] + 1;
                q.add(x+1);
            }

            if(x * 2 <= 100_000 && !visit[x*2]){
                visit[x*2] = true;
                dist[x * 2] = dist[x] + 1;
                q.add(x * 2);
            }
        }
    }
}