[백준-1697번] 숨바꼭질 풀이 - Java

 

🚀 문제

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

 

🚀 접근 방법

 총 3가지 이동 방법이 있다.

1. x-1

2. x+1

3. 2x

 

각각의 이동 경로를 Queue에 추가하고 조건에 부합하면 그때의 count를 return하면 된다.

 

DFS로 푸는것보다 BFS로 푸는 것이 최단거리 찾는데 적합하다.(성능 측면)

 

🚀 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int[] numbers = Arrays.stream(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int n = numbers[0];
        int k = numbers[1];

        if(n==k){
            System.out.println(0);
            return;
        }

        boolean[] visit = new boolean[100001];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);

        int count=0;

        while(!queue.isEmpty()) {
            int size = queue.size();
            count++;

            for(int i=0; i<size; i++) {
                int node = queue.remove();
                visit[node] = true;
                if(node-1 == k ||node*2==k || node+1==k){
                    System.out.println(count);
                    return;
                }

                if(node-1>=0&& !visit[node-1]){
                    visit[node-1]=true;
                    queue.add(node-1);
                }

                if(node+1<=100000 && !visit[node+1]){
                    visit[node+1]=true;
                    queue.add(node+1);
                }
                if(node*2<=100000 && !visit[node*2]){
                    visit[node*2]=true;
                    queue.add(node*2);
                }
            }
        }


        System.out.println(count);
    }
}