boj 17071: 숨바꼭질 5

수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다.

• 수빈이가 움직이는 방법: X - 1, X + 1, 2 * X
• 동생이 움직이는 방법: K + 1 + 2 + 3 + ... + i
• 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

수빈이가 왼쪽한번 오른쪽한번 이동하게 되면 제자리로 돌아오기 때문에, 짝수/홀수 시간마다 갈 수 있는 곳을 나누어 시간을 저장한다.

만약 동생이 지나가는 좌표값에 수빈이가 처음 도착하는 시간이 더 빠를 경우 답을 업데이트 해 주도록 한다.

import java.util.*;

public class Main {
	public static int INF = 500000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int indexSubin = in.nextInt();
		int indexSister = in.nextInt();

		int isVisited[][] = new int[INF + 1][2];
		for (int i = 0; i <= INF; i++) {
			isVisited[i][0] = -1;
			isVisited[i][1] = -1;
		}

		moveSubin(isVisited, indexSubin);
		System.out.println(moveSister(isVisited, indexSister));
	}

	public static void moveSubin(int[][] isVisited, int start) {
		Queue<Move> queue = new LinkedList<Move>();
		queue.add(new Move(start, 0));
		isVisited[start][0] = 0;

		while (!queue.isEmpty()) {
			Move now = queue.poll();

			int nextTime = now.time + 1;
			checkBoundaryAndPushQueue(isVisited, queue, now.index - 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index + 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index * 2, nextTime);
		}
	}

	public static void checkBoundaryAndPushQueue(int[][] isVisited, Queue<Move> queue, int index, int time) {
		if (isBoundary(index) && isVisited[index][time % 2] == -1) {
			queue.add(new Move(index, time));
			isVisited[index][time % 2] = time;
		}
	}

	public static int moveSister(int[][] isVisited, int start) {
		for (int time = 0; time < INF; time++) {
			int index = start + time * (time + 1) / 2;

			if (index > INF) {
				return -1;
			}

			if (isVisited[index][time % 2] != -1 && isVisited[index][time % 2] <= time) {
				return time;
			}
		}
		return -1;
	}

	public static boolean isBoundary(int index) {
		if (index < 0) {
			return false;
		}
		if (index > INF) {
			return false;
		}
		return true;
	}
}

class Move {
	int index;
	int time;

	public Move(int index, int time) {
		this.index = index;
		this.time = time;
	}

	@Override
	public String toString() {
		return "(" + index + ": " + time + ")";
	}
}