[백준] 1697 숨바꼭질 java

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

class Node {
    int num;
    int cnt;
    Node(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}

public class HideAndSeek {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, K;
    static int ans;
    static boolean[] checked;


    public static void main(String[] args) throws IOException{
        input();
        solve();
        System.out.println(ans);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        ans = Integer.MAX_VALUE;
        checked = new boolean[100001];
    }

    public static void solve() {
        Queue<Node> q = new LinkedList<>();
        //큐에 시작 숫자인 N을 넣고 방문처리를 해준다.
        q.add(new Node(N, 0));
        checked[q.peek().num] = true;

        //bfs로 돌면서 수를 찾는다.
        while (true) {
            int num = q.peek().num;
            int numCnt = q.poll().cnt;
            if(num == K) {
                ans = numCnt;
                break;
            }

            //인덱스 에러가 나기 때문에 경계값 처리를 해준다.
            if(num-1 >= 0){
                if(!checked[num-1]) {
                    q.add(new Node(num-1, numCnt+1));
                    checked[num-1] = true;
                }
            }
            if(num+1 <= 100000){
                if(!checked[num+1]) {
                    q.add(new Node(num+1, numCnt+1));
                    checked[num+1] = true;
                }
            }

            if(num*2 <= 100000) {
                if(!checked[num*2]) {
                    q.add(new Node(num*2, numCnt+1));
                    checked[num*2] = true;
                }
            }
        }
    }
}

BFS 문제이다. 처음에는 DFS를 사용해 재귀적으로 탐색하는 것을 시도했으나 StackoverflowError가 일어나서 생각해보니 무척 비효율적이란걸 깨달았다. 그래서 이건 bfs로 돌아야겠구나 생각하고 코드를 수정했다. 하지만 경계값인 N = 100000, K = 0이 주어졌을 때, 2초 이상이 걸리는걸 보고 최적화를 해야겠다고 생각했다.

 

우선 트리로 그려서 경우의 수를 봤더니 -, +, * 과정에서 이미 방문했던 수를 다시 방문해서 중복되는 경우의 수를 계속해서 돌고있는게 무척 비효율적이였다. 그래서 방문처리를 해서 한번 방문했던 수는 다시 안해도 되게끔 해줬다.

 

그리고 마지막으로 경계값 처리를 해서 인데싱에러가 나지 않도록 해주었다.