[알고리즘][BOJ][1697] 숨바꼭질

 

[알고리즘][BOJ][1697] 숨바꼭질

 

 

문제

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

 

 

풀이

BFS를 이용해서 문제를 풀었어요. 

최단 경로를 찾아야 하기 때문에 DFS를 이용했다가 무한루프에 빠져서 BFS로 방법을 바꿨습니다. 큐에 넣고 이동할 때마다 시간을 함께 카운팅하여 넣어주는 방식으로 풀었는데 다른 문제에서도 유사한 방식으로 풀었던 기억이 납니다! 잘 기억해놨다가 다음에는 삽질하지 않도록 해야겠네요!

 

코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int[] check = new int[100001];
        Arrays.fill(check, -1);
        System.out.println(BFS(n, k, check));
    }
    static int BFS(int n, int k, int[] check) {
        Queue<Integer> queue = new LinkedList<>();
        int next_x = n;
        queue.add(next_x);
        check[next_x] = 0;
        int[] move = new int[3];
        
        while(!queue.isEmpty() && next_x!=k) {
            next_x = queue.poll();
            
            move[0] = next_x + 1;
            move[1] = next_x - 1;
            move[2] = next_x * 2;
            
            for(int i=0;i<3;i++) {
                if(move[i]>=0 && move[i]<=100000) {
                    if(check[move[i]]==-1) {
                        queue.add(move[i]);
                        check[move[i]]=check[next_x]+1;
                    }
                }
            }
            
        }
        return check[k];
    }
}