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

---

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

---

📌 문제

문제 유형

• 그래프

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입출력 예시

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

5 17

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

4

🔍 문제 풀이

1. BFS를 활용하여 최단 시간을 탐색한다.
2. 수빈이의 위치 n을 시작점으로 큐에 넣고 방문 처리
3. 매 루프마다 현재 위치에서 이동할 수 있는 세 위치(-1, +1, *2)를 계산
4. 이미 방문한 위치는 스킵하며, 처음 도달한 위치는 time 배열에 거리(시간) 저장
5. 목표 위치 m에 도달하면 해당 위치의 시간을 반환한다.

예시

초기 상태: 수빈이 위치 5 → 동생 위치 17까지 최단 시간 탐색

1. time[5] = 0, visited[5] = true
   • 1초 후 → 이동 가능: 4, 6, 10
     
     
2. time[4] = 1, time[6] = 1, time[10] = 1
   • 2초 후 → 이동 가능: 3, 7, 9, 12, 20
     
     
3. time[3] = 2, time[7] = 2, …
   
   
4. … 계속 탐색
   
   
5. 최종적으로 time[17] = 4

최종 결과: 4초

💭 놓친 점

놓친 점 1)

이번 문제는 2차원 격자가 아니라 1차원 배열 형태의 그래프라서 처음에 더 헷갈렸던 것 같다.

이 문제에선 그냥 X-1, X+1, 2*X만 고려하면 됨.

놓친 점 2)

처음에 MAX = 100_001 이렇게 설정한 게 왜 필요한지 잘 몰랐는데,

인덱스를 100,000까지 다뤄야 하니까 배열 크기를 100,001로 둔 거였음. 이렇게 미리 최대 범위를 잡아두면 인덱스 범위 벗어나는 걸 방지할 수 있음.

놓친점 3)

int[] nextPositions = {current - 1, current + 1, current * 2};

이렇게 연산한 걸 배열로 받을 수 있다는 생각을 못함.

💻 전체 코드

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

public class Main {
    static int n, m;
    static final int MAX = 100_001;
    static int[] time; // 걸린 시간 저장
    static boolean[] visited; // 방문 여부 체크

    public static int bfs() {


        Deque<Integer> dq = new ArrayDeque<>();
        dq.offer(n);
        visited[n] = true;

        while (!dq.isEmpty()) {
            int current = dq.poll();

            if (current == m) { // 도착했을 때
                return time[current];
            }

            int[] nextPositions = {current - 1, current + 1, current * 2};
            for (int next : nextPositions) {
                if (next < 0 || next >= MAX) continue;
                if(!visited[next]){
                    dq.offer(next);
                    visited[next] = true;
                    time[next] = time[current] + 1; // 현재 위치(current)까지 걸린 시간에 +1초를 더해, 다음 위치(next)의 시간을 저장
                }

            }
        }
        return -1; // 도달할 수 없는 경우
    }

    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()); // 수빈 위치
        m = Integer.parseInt(st.nextToken()); // 동생 위치

        time = new int[MAX];
        visited = new boolean[MAX];

        int result = bfs();
        System.out.println(result);
    }
}