[1697] 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제 해결 방법

bfs를 사용해서 구현했다.

2%쯤에서 실패가 떴는데, N == K 일 때 바로 끝내도록 해서 통과할 수 있었다. 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, K, answer;
    static boolean flag;
    static boolean[] visit;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        flag = false;
        visit = new boolean[100001];

        hideAndSeek();

        System.out.println(answer);
    }

    public static void hideAndSeek() {
        if(N == K) return;

        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        visit[N] = true;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            cnt++;
            for (int i = 0; i < size; i++) {
                int cur = q.poll();

                if (chk(cur * 2)) { // 순간이동 해볼까
                    q.add(cur * 2);
                    visit[cur * 2] = true;
                }
                if (chk(cur + 1)) { // 한 칸 앞으로 가볼까
                    q.add(cur + 1);
                    visit[cur + 1] = true;
                }
                if (chk(cur - 1)) { // 한 칸 뒤로 가볼까
                    q.add(cur - 1);
                    visit[cur - 1] = true;
                }

                if (flag) {
                    answer = cnt;
                    return;
                }
            }
        }
    }

    public static boolean chk(int idx) {
        if (idx == K) {
            flag = true;
        }
        return idx >= 0 && idx <= 100000 && !visit[idx];
    }
}