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

• 백준 문제 URL

---

문제 요약

수빈이의 현재 위치 n에서 동생 위치 k로 이동하려고 한다.
한 번에 할 수 있는 이동은 딱 3가지다.

• x -> x - 1
• x -> x + 1
• x -> x * 2

이때 동생을 찾는(= k에 도달하는) 최소 시간(최소 이동 횟수) 을 출력하는 문제다.

---

핵심 아이디어

이 문제는 “한 번 이동할 때마다 비용이 1로 동일”한 최단거리 문제라서 BFS가 정답이다.
BFS는 레벨(거리) 순으로 탐색하므로, 어떤 위치를 처음으로 방문하는 순간이 곧 그 위치까지의 최단 시간이다.

추가로 이 문제는 간선 목록이 입력으로 주어지는 게 아니라, 현재 위치 x에서 다음 상태 {x-1, x+1, 2x}가 “규칙”으로 생성되는 유형이라 큐 기반 BFS가 특히 잘 맞는다.

---

상태 설계(큐에 뭘 넣을까?)

코드에서는 Queue<int[]>를 사용해서 아래 상태를 같이 들고 간다.

• int[]{position, time}
  • position: 현재 위치
  • time: 현재 위치까지 오는데 걸린 시간(이동 횟수)

Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{n, 0});

이렇게 하면 큐에서 꺼낼 때마다 “이 위치에 도달한 시간”을 바로 알 수 있어서 거리 배열 없이도 구현이 단순해진다.

---

방문 처리(visited)가 중요한 이유

visited가 없으면 같은 위치가 여러 경로로 계속 큐에 들어가서 탐색이 폭발한다.
그래서 큐에 넣는 순간 visited[nx] = true로 확정해서 중복 삽입을 막는다.

boolean[] visited = new boolean[100000 + 1];
visited[n] = true;

여기서 배열 크기를 100000 + 1로 둔 이유는 문제에서 위치 범위가 0~100000으로 제한되기 때문이다.

---

BFS 진행 흐름

1) 큐에서 하나 꺼낸다 (x, time)
2) x == k면 time이 최단시간이므로 즉시 출력하고 종료
3) 다음 후보 {x-1, x+1, x*2}를 만든다
4) 범위(0~100000) 안이고 아직 방문 안 했으면

• 방문 처리하고
• time+1로 큐에 넣는다

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

    if (x == k) {
        System.out.println(time);
        return;
    }

    int[] next = {x - 1, x + 1, x * 2};
    for (int nx : next) {
        if (nx >= 0 && nx <= 100000 && !visited[nx]) {
            visited[nx] = true;
            queue.add(new int[]{nx, time + 1});
        }
    }
}

예외 처리: 시작부터 같은 경우

n == k면 이동이 필요 없으니 바로 0을 출력하는 게 깔끔하다.

---

전체 코드(제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    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<int[]> queue = new LinkedList<>();
        queue.add(new int[]{n, 0});

        boolean[] visited = new boolean[100000 + 1];
        visited[n] = true;

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

            if (x == k) {
                System.out.println(time);
                return;
            }

            int[] next = {x - 1, x + 1, x * 2};
            for (int nx : next) {
                if (nx >= 0 && nx <= 100000) {
                    if (!visited[nx]) {
                        visited[nx] = true;
                        queue.add(new int[]{nx, time + 1});
                    }
                }
            }
        }
    }
}