[백준] 17071 숨바꼭질 5 (JAVA)

문제 링크:

17071번: 숨바꼭질 5

 

 

난이도: 플레티넘  5

 

 

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

 

입력:

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

 

 

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

 

문제 이해:

이 문제는 수빈이의 위치 N과 동생의 위치 K가 주어졌을 때, 수빈이는 매 초마다 +1, -1, 또는 ×2 만큼 이동할 수 있다고 가정한다.

동생 역시 초마다 앞으로 이동하는데, 이동 거리는 가속적으로 증가한다. 즉, 1초 후에는 +1, 2초 후에는 +1+2, 3초 후에는 +1+2+3 만큼 이동하게 된다.

 

쉬운 이해를 위해 예제 입력 1을 통해 살펴보자.

수빈이가 위치 5, 동생이 위치 17에 있다고 하면, 수빈이는 5 → 10 → 20으로 이동하고, 동생은 17 → 18 → 20으로 이동한다. 따라서 두 사람은 가장 빠르게 2초 후에 만나게 된다.

 

 

구현 방향:

작성자는 BFS로 문제를 풀고자 했으나, 동일 좌표를 여러 번 방문할 수 있는 특성 때문에 단순 방문 배열만 사용하면 메모리 초과가 발생할 수 있다.

이를 해결하려면 도달 시간의 짝/홀을 분리해 상태를 관리한다. 즉 visited[pos][time % 2] 형태로 “해당 좌표에 정확히 짝수(0)/홀수(1) 초에 도달 가능”을 기록하고, 매 초의 시작에 동생의 위치와 대조하여 만남 여부를 판단한다.

 

간단한 예시를 통해 이해를 해보면 다음과 같다.

 

초기 상태: 수빈 N=5, 동생 K=17

• t=0 (짝)
  • 수빈 가능 좌표: {5} → visited[5][0] = true
  • 동생 위치: 17 + 0 = 17
  • 만남 여부: visited[17][0]? → false
• t=1 (홀)
  • 수빈이 한 번 움직여 도달 가능한 좌표를 표시: {4, 6, 10}
    • visited[4][1] = visited[6][1] = visited[10][1] = true
  • 동생 위치: 17 + 1 = 18
  • 만남 여부: visited[18][1]? → false
• t=2 (짝)
  • 수빈이 두 번 움직여 도달 가능한 좌표를 표시(일례): {… , 20, …}
    • (예 경로: 5 → 10 → 20) → visited[20][0] = true
  • 동생 위치: 17 + (1+2) = 20
  • 만남 여부: visited[20][0]? → true ⇒ 정답은 2초

수빈이는 5 → 10 → 20, 동생은 17 → 18 → 20으로 이동하므로, 2초 후 좌표 20에서 만난다.
위 과정에서 visited[pos][time%2]는 “정확히 그 시간대(짝/홀)에 그 좌표에 도달할 수 있음”을 뜻하므로, 매 초 시작 시 동생 위치 broPos = K + t(t+1)/2에 대해 visited[broPos][t%2]를 확인하면 만남을 판정할 수 있다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

정답코드:

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 {
    static int N, K;
    static boolean[][] visited = new boolean[500001][2]; // visited[pos][time%2]

    public static int solve(int pos) {
        Queue<int[]> q = new LinkedList<>();
        // queue : 현재 위치, 현재 시간, 동생 가속 누적
        q.add(new int[]{pos, 0, 0});
        visited[pos][0] = true; // 시작점 방문 표시(짝수 시간)

        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int curPos = arr[0];
            int curTime = arr[1];
            int curSpeed = arr[2]; // t(t+1)/2 누적값

            // 현재 시간의 동생 위치
            int broPos = K + curSpeed;
            if (broPos > 500000) return -1;

            // 같은 시간대에 도달 가능한 모든 칸 중 broPos가 포함되면 만남
            if (visited[broPos][curTime % 2]) return curTime;

            // 아래는 다음 시간대로 전이
            int nextTime = curTime + 1;
            int nextParity = nextTime % 2;
            int nextSpeed = curSpeed + nextTime;

            // +1 이동
            if (curPos < 500000 && !visited[curPos + 1][nextParity]) {
                visited[curPos + 1][nextParity] = true;
                q.add(new int[]{curPos + 1, nextTime, nextSpeed});
            }
            // -1 이동
            if (curPos > 0 && !visited[curPos - 1][nextParity]) {
                visited[curPos - 1][nextParity] = true;
                q.add(new int[]{curPos - 1, nextTime, nextSpeed});
            }
            // *2 이동
            if (curPos * 2 <= 500000 && !visited[curPos * 2][nextParity]) {
                visited[curPos * 2][nextParity] = true;
                q.add(new int[]{curPos * 2, nextTime, nextSpeed});
            }
        }
        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());
        K = Integer.parseInt(st.nextToken());

        // 탐색 시작
        int result = solve(N);

        // 결과 출력
        System.out.println(result);
    }
}

 

 

 

마무리하며:

작성자는 처음에 단순 BFS로 접근했다가 메모리 초과를 경험하였다. 이후 짝/홀 분리 아이디어를 스스로 떠올리지 못해 관련 블로그 자료를 참고했고, 이를 통해 문제를 해결할 수 있었다.

이 경험을 통해 문제 해결 과정에서 단순 구현이 아니라, 상태 공간을 어떻게 효율적으로 관리할지 고민하는 사고력이 중요함을 깨달았다.

 

 

감사합니다.