[BOJ] 백준 1697번 : 숨바꼭질 - Java

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

 

• BFS
  • N이 움직이는 위치와 걸리는 시간을 다뤄야하므로 class Node를 정의하여 사용
  • pos가 이동가능한 위치는 1초가 증가할 때마다 pos-1, pos+1, pos*2의 세 가지 경우를 고려

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

public class Main {
    static class Node {
        int position;   // 현재 위치
        int time;       // 걸린 시간

        public Node(int pos, int time) {
            this.position = pos;
            this.time = time;
        }
    }
    static int N;
    static int K;
    static Queue<Node> queue = new LinkedList<>();
    static boolean[] visited = 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(), " ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        queue.offer(new Node(N, 0));
        visited[N] = true;
        bfs();
    }
    public static void bfs() {
        // 큐가 빌때까지 반복 (가능한 모든 위치를 탐색할 때 까지 반복)
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            int pos = currentNode.position;
            int time = currentNode.time;

            // 현재 위치가 K와 같다면, 탐색 종료 후 시간 반환
            if (pos == K) {
                System.out.println(time);
                break;
            }

            // 현재 위치에서 이동 가능한 세 가지 위치를 계산
            int[] nextPos = {pos-1, pos+1, pos*2};
            for (int next : nextPos) {
                // position의 범위가 0 <= pos <= 100000이고, 방문한 적 없는 위치인지 확인
                if (next >= 0 && next <= 100000 && !visited[next]) {
                    visited[next] = true;   // 방문 처리
                    queue.offer(new Node(next, time + 1));  // queue에 새로운 위치 삽입
                }
            }
        }
    }
}