https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
Solve
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] input;
static int[] memo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
input = new int[2];
input[0] = Integer.parseInt(st.nextToken());
input[1] = Integer.parseInt(st.nextToken());
memo = new int[100001];
Arrays.fill(memo, -1);
BFS();
System.out.println(memo[input[1]]);
}// main end
public static void BFS() {
Queue<Integer> queue = new LinkedList<>();
queue.offer(input[0]);
memo[input[0]] = 0;
while (!queue.isEmpty()) {
if (memo[input[1]] != -1)
return;
int d = queue.poll();
if (d+1 < 100001 && memo[d + 1] == -1) {
queue.offer(d+1);
memo[d + 1] = memo[d] + 1;
}
if (d-1 >= 0 && memo[d - 1] == -1) {
queue.offer(d-1);
memo[d - 1] = memo[d] + 1;
}
if (d*2 < 100001 && memo[d * 2] == -1) {
queue.offer(d*2);
memo[d * 2] = memo[d] + 1;
}
}// while end
}// method end
}
이동한 시간을 기록하면서 BFS를 돈다.
반응형