[BOJ] 백준 1697 - 숨바꼭질 (자바)

BFS? DFS?

알고리즘 분류에는 DFS도 나와있는데, DFS로는 어떻게 풀지 모르겠다. 

DFS로 푸니까 스택오버플로우가.....................................

므즈건 BFS로 푸는게 나을거 같다.

풀때는 굉장히 어려운 문제였는데 풀고나니까 쉬워보인다. 그렇게 어려운 문제는 아님;

풀이

1. 다음에 이동할 위치 앞으로 한칸 (+1), 뒤로 한칸 (-1), 순간이동 (x2) 을 생각해준다.

2. 조건에 맞는지 확인한다. 조건이란 배열을 벗어나지 않았는지, 이전에 방문했던점이 아닌지 이다. 모든 배열을 -1로 놓고 변하지 않았다면 이동 X

선입선출이므로 해당 위치에 먼저 도착한놈이 무조건 빠르거나 같다. (이동 횟수가 작다) 그렇기 때문에 이전에 방문했던점이면 굳이 갈 필요가 없다.

나는 이조건에서 헤맴..

3. 조건에 맞다면 이동할 위치 3개로 모두 이동한다. (큐를 이용한다.)

4. 큐에서 다시 하나씩 빼가면서 도착할 때 까지 반복한다.

코드

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[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] Min = new int[100005];
        Arrays.fill(Min, -1);    //초기값을 다 -1로 설정
        System.out.println(BFS(N, K, Min));
 
    }
 
    public static int BFS(int N, int K, int[] Min) {
        int nextN = N;
        int[] status = new int[3];
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(nextN);
        Min[nextN] = 0;
 
        while (!q.isEmpty() && nextN != K) {
 
            nextN = q.poll();
            //다음에 이동할 좌표들
            status[0] = nextN - 1;     //뒤로 한칸
            status[1] = nextN + 1;    //앞으로 한칸
            status[2] = nextN * 2;    //순간이동
 
            for (int i = 0; i < 3; i++) {
                //배열을 벗어나지 않았는지 확인
                if (status[i] >= 0 && status[i] <= 100000) {
                    //이전에 방문했는지 확인
                    if (Min[status[i]] == -1) {
                        //처음 간 곳이라면 큐에 넣고 상태를 전 위치값 +1 을 해준다.
                        q.add(status[i]);
                        Min[status[i]] = Min[nextN] + 1;
 
                    }
                }
            }
        }
        return Min[K];
    }
}