[백준 1697번 / Java] 숨바꼭질 - BFS

문제 링크

Silver 1

 

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

1697번: 숨바꼭질

 

 

---

 

 

풀이

단순 BFS 구현 문제로 너비를 +1, -1, *2의 경우로 두었고 문제 조건에 알맞게 예외상황에 대한 처리를 하면 되는데

 

N == K일 때의 상황을 고려하지 않아서 20분동안 삽질했다..

꼼꼼하게 보고 놓치지 말자..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BaekJoon1697 {

    private static boolean[] bl = new boolean[100001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        if(N == K) {
            System.out.println(0);
            return;
        }

        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        bfs(que, 0, K);

    }

    private static void bfs(Queue<Integer> que, int time, int K) {
        while(!que.isEmpty()) {
            int size = que.size();
            time++;

            for(int i = 0; i < size; i++) {
                int now = que.poll();
                bl[now] = true;

                if(now + 1 == K || now - 1 == K || now * 2 == K) {
                    System.out.println(time);
                    return;
                }
                if(now + 1 <= 100000 && !bl[now + 1]) {
                    que.add(now + 1);
                    bl[now + 1] = true;
                }
                if(now - 1 >= 0  && !bl[now - 1]) {
                    que.add(now - 1);
                    bl[now - 1] = true;
                }
                if(now * 2 <= 100000  && !bl[now * 2]) {
                    que.add(now * 2);
                    bl[now * 2] = true;
                }
            }
        }
        System.out.println(time);
    }

}