문제 링크 : https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는
www.acmicpc.net
숨바꼭질 시리즈의 세번째 문제입니다.
이번에는 수빈이가 동생을 만나는 최단 시간을 찾는 문제이지만, *2를 0초만에 이동할 수 있다는 점이 다릅니다.
역시 BFS를 이용해서 풀었으며 -1, +1 하는 위치를 구하기 전에 *2인 위치를 먼저 계산했습니다.
단순히 *2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둡니다.
그러면 시간이 작은 노드들이 무조건 Queue에 먼저 들어가게 됩니다.
이 문제를 푸는데 굉장히 많은 시도를 하였습니다.
처음에는 제 생각이 잘못되었나 해서 우선순위큐를 써보기도 하고 중복 방문에 대해서 계산도 하였습니다.
그런데 고생한 보람에 비해 해결은 굉장히 싱거웠습니다.
*2를 계산한 후에 저는 +1, -1 순서대로 계속 Queue에 넣었는데 -1, +1 순서로 바꾸니까 통과하였습니다.
정확히 계산을 해보진 않았지만 +1을 먼저 Queue에 넣게 되면 -k 만큼 이동한 후에 *2 를 한 경우를 간과하고 끝날 수 있는 것 같습니다.
예시로 들면 4 6 이라는 입력이 들어오면 +1 +1 이동보다 -1 *2 이동 시간이 더 작습니다.
하지만 Queue에 넣는 순서에 따라서 결과값이 달라질 수 있으니 앞으로는 좀 더 생각하며 로직을 짜야 할 것 같습니다.
<Java>
import java.util.*;
import java.io.*;
// https://www.acmicpc.net/problem/13549
class Main {
static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = stoi(st.nextToken());
int K = stoi(st.nextToken());
if(N >= K)
System.out.println(N-K);
else
System.out.println(BFS(N, K));
}
static int BFS(int N, int K) {
Queue q = new LinkedList();
int[] subin = new int[100001];
Arrays.fill(subin, -1);
q.add(N);
subin[N] = 0;
while(!q.isEmpty()) {
int now = q.poll();
// 동생을 만나면 끝
if(now == K)
return subin[now];
// *2 인 거리 중 방문하지 않은 곳 전부 체크
int temp = now * 2;
while(temp <= 100000 && subin[temp] == -1) {
subin[temp] = subin[now];
q.add(temp);
temp *= 2;
}
for(int i=0; i<2; i++) {
int next;
if(i == 0)
next = now - 1;
else
next = now + 1;
if(0 <= next && next <= 100000) {
if(subin[next] == -1) {
q.add(next);
subin[next] = subin[now] + 1;
}
}
}
}
return 0;
}
}