[코딩테스트/백준 알고리즘] 1697번 - 숨바꼭질 (Java, 자바 풀이)

문제

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

1697번: 숨바꼭질

---

문제 설명

---

문제 풀이

N을 기준으로 N - 1, N +1, N * 2 의 수를 그래프로 만들어서 큐에 넣고 너비우선탐색를 수행한다.

---

코드

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

class Main {
    static int[] visit = new int[100001];
    static Queue<Integer> q = new LinkedList<>();
    static int start;
    static int finish;
    static int result;

    static void BFS() {
        while(!q.isEmpty()) {
            int node = q.poll();
            if (node == finish) {
                result = visit[node] + 1;
                break;
            }
            int[] make = {-1, +1, node};
            for(int i : make) {
                if(node + i >= 0 && node + i <= 100000) {
                    if(visit[node + i] == -1) {
                        q.offer(node + i);
                        visit[node + i] = visit[node] + 1;
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        finish = Integer.parseInt(st.nextToken());
        Arrays.fill(visit, -1);
        q.offer(start);
        BFS();
        System.out.println(result);

    }
}