백준 17071번: 숨바꼭질 5 (JAVA)

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

17071번: 숨바꼭질 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에 X번만에 왔다면, X+2, X+4, .. 번째에도 N에 있을 수 있다.;'

 

 

풀이

동생도 움직이기에, 단순히 bfs를 써서 어떤 위치까지 이동하는 최소 시간만 구한다면 모든 경우를 놓칠 수 있다. 모든걸 기록한다는 관점으로 boolean 이차원 배열 [위치][현재시간]을 만들어 (위치, 현재시간)에 대해 수빈이가 있을 수 있따면 true로 하는 풀이를 생각해 볼 수 있으나, 위치 <= 50만, 현재시간 <= (대략 sqrt(50만))이므로 시간 초과는 둘째치고, 일단 메모리 초과가 뜰 것이다.

힌트를 이용한 풀이: 특정 위치 N에 최소로 도달하는 '짝수 소요시간'과 '홀수 소요시간'을 기록한다. 예를 들어, 5에 도달하는데 '최소 짝수 소요시간'은 4, '최소 홀수 소요시간'이 7이라면, 4, 6, 8, 10, ... , 그리고 7, 9, 11, ...인 시간에는 해당 위치에 있을 수 있다. 따라서, 각 소요시간마다 동생의 위치에 대하여 현재 소요시간보다 작으며 현재 소요시간과 홀짝성이 같은 도착 기록이 있다면 해당 위치에서 수빈이는 동생을 만날 수 있다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
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));
        int[][] dist = new int[2][500001];
        Arrays.fill(dist[0], -1);
        Arrays.fill(dist[1], -1);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        dist[0][N] = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {N, 0});

        if (N == K) {
            System.out.println(0);
            return;
        }
        int time = 0;
        while (!queue.isEmpty()) {
            time++;
            K += time;
            if (K > 500000) break;
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.poll();
                int loc = cur[0], len = cur[1];
                if (2*loc <= 500000 && dist[(len+1)%2][2*loc] < 0) {
                    dist[(len+1)%2][2*loc] = len+1;
                    queue.offer(new int[] {2*loc, len+1});
                } 
                if (loc+1 <= 500000 && dist[(len+1)%2][loc+1] < 0) {
                    dist[(len+1)%2][loc+1] = len+1;
                    queue.offer(new int[] {loc+1, len+1});
                }
                if (loc-1 >= 0 && dist[(len+1)%2][loc-1] < 0) {
                    dist[(len+1)%2][loc-1] = len+1;
                    queue.offer(new int[] {loc-1, len+1});
                }
            }
            if (dist[time%2][K] >= 0) {
                System.out.println(time);
                return;
            }
        }
        System.out.println(-1);
    }
}