https://www.acmicpc.net/problem/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;
static int answer = 0;
static boolean[] visited;
static class Point {
int v, cnt;
public Point(int v, int cnt) {
this.v = v;
this.cnt = cnt;
}
}
static boolean check(int x) {
if (x < 0 || x > 100000 || visited[x]) return false;
return true;
}
static void bfs(int v) {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(v, 0));
visited[v] = true;
while (!queue.isEmpty()) {
Point p = queue.poll();
int x = p.v;
int cnt = p.cnt;
if (x == k) {
answer = cnt;
break;
}
if (check(x-1)) {
queue.add(new Point(x - 1, cnt + 1));
visited[x - 1] = true;
}
if (check(x+1)) {
queue.add(new Point(x + 1, cnt + 1));
visited[x + 1] = true;
}
if (check(x*2)) {
queue.add(new Point(x * 2, cnt + 1));
visited[x * 2] = true;
}
}
}
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()); // 동생
// 걸으면 1초후에 x-1 또는 x+1로 이동
// 순간이동시에는 1초 후에 2*X의 위치로 이동
visited = new boolean[100001];
bfs(n);
System.out.println(answer);
}
}
1초 후에 갈 수 있는 좌표 3가지의 경우를 큐에 집어놓고 BFS 탐색을 진행한다.
이 때, 가장 최소 시간을 구해야하므로 이미 방문했던 좌표는 굳이 또 방문하지 않게 하기 위해 visit 배열에다 체크한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 13549번- 숨바꼭질 3 (0) | 2023.01.09 |
---|---|
[JAVA] 백준 13913번- 숨바꼭질 4 (0) | 2023.01.09 |
[JAVA] 백준 1707번- 이분 그래프 (0) | 2023.01.06 |
[JAVA] 백준 1987번- 알파벳 (0) | 2023.01.06 |
[JAVA] 백준 2580번- 스도쿠 (0) | 2023.01.06 |