[백준 1697] 숨바꼭질 - JAVA

과거에 풀었던 문제입니다. 노션에 기록된 내용을 바탕으로 정리했습니다.

문제 정의

문제 정의

• 수빈이의 현재 위치를 x 라고 할 때 수빈이가 한 번 움직일 때 도달할 수 있는 위치는 x-1 x+1 x*2 일 때
• 동생을 찾는데 걸리는 최단 시간을 구해라

제한 사항

• 수빈이의 위치 $(N)$
  • $0≤N≤100,000$
• 동생의 위치 $(K)$
  • $0≤K≤100,000$

출력

최단 시간 출력

접근 방법

1차원 그래프 탐색 문제

• $BFS, DFS$ 전부 가능하지만 최단 시간을 구하는 문제이므로 $BFS$가 가장 효율적
• 1차원 $BFS$도 다른 것은 없습니다.
  • 행에 대한 케이스를 없애고 다음 이동할 수 있는 dx를 구하는 것이 중요
    • 해당 문제의 dx ⇒ dx = {-1, 1, x}
  • 주의해야 될 사항 ⇒ 어떤 테스트 케이스든 영역의 범위는 $0 \leq area \leq100,000$ 이므로 주의할 것!

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int K;
    static int[] dx = {-1, 1, 0};
    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) System.out.println(N-K);
        else System.out.println(bfs());
    }

    static int bfs() {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{N, 1});
        visited[N] = true;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int t = tmp[1];

            if (x == K) {
                return t-1;
            }

            dx[2] = x;
            for (int i = 0; i < 3; i++) {
                int nx = x + dx[i];
                if (0 <= nx && nx <= 100000 && !visited[nx]) {
                    visited[nx] = true;
                    queue.add(new int[]{nx, t+1});
                }
            }
        }
        return -1;
    }
}