백준 [1697] 숨바꼭질
문제보기
풀이방법
소스코드
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, ans;
static Queue<int[]> queue;
static int[] v;
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());
ans = 987654321;
queue = new LinkedList<>();
v = new int[100001];
queue.add(new int[] { N, 0 });
v[N] = -1;
if (N == K)
ans = 0;
else
find();
if (ans == 987654321)
ans = -1;
System.out.println(ans);
};
public static void find() {
while (!queue.isEmpty()) {
int[] q = queue.poll();
if (ans <= q[1])
continue;
// 걷는경우
int pre = q[0] - 1;
if (pre == K) {
ans = Math.min(ans, q[1] + 1);
continue;
} else if (pre >= 0) {
if (v[pre] == 0 || v[pre] > q[1] + 1) {
queue.add(new int[] { pre, q[1] + 1 });
v[pre] = q[1] + 1;
}
}
int next = q[0] + 1;
if (next == K) {
ans = Math.min(ans, q[1] + 1);
continue;
} else if (next <= 100000) {
if (v[next] == 0 || v[next] > q[1] + 1) {
queue.add(new int[] { next, q[1] + 1 });
v[next] = q[1] + 1;
}
}
// 순간이동 하는 경우
int jump = 2 * q[0];
if (jump == K) {
ans = Math.min(ans, q[1] + 1);
continue;
} else if (jump >= 0 && jump <= 100000) {
if (v[jump] == 0 || v[jump] > q[1] + 1) {
queue.add(new int[] { jump, q[1] + 1 });
v[jump] = q[1] + 1;
}
}
}
}
}