문제 분석
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import java.io.*;
import java.util.*;
class Main {
// 방문 배열 초기화, N, K의 최대 범위는 최대 100,000이다.
static int[] visited = new int[100001];
static int N;
static int K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// BFS 함수 호출하여 N~K까지의 최소시간 계산
int result = BFS(N);
bw.write(result+"\n");
bw.close();
br.close();
}
static int BFS(int node) {
Queue<Integer> q = new LinkedList<>();
q.offer(node);
// N 위치는 1초부터 시작하기에 visited[N] 위치에 1로 초기화
visited[node] = 1;
while(!q.isEmpty()) {
int now = q.poll();
// BFS를 통해 K까지 탐색이 완료되면 반환
if(now == K) {
return visited[now]-1;
}
// walk_back: 현재 위치-1 위치가 0보다 크고 방문하지 않았다면
// -1 위치에 +1초를 저장하고 -1 위치를 큐에 저장
if(0<=(now-1) && visited[now-1]==0) {
visited[now-1] = visited[now]+1;
q.add(now-1);
}
// walk_forward: 현재 위치+1 위치가 100,000 보다 작고 방문하지 않았다면
// +1 위치에 +1초를 저장하고 +1 위치를 큐에 저장
if((now+1)<=100000 && visited[now+1]==0) {
visited[now+1] = visited[now]+1;
q.add(now+1);
}
// warp: 현재위치*2 위치가 100,000보다 작거나 방문하지 않았다면
// *2 위치에 +1초를 저장하고 *2 위치를 큐에 저장
if((now*2)<=100000 && visited[now*2]==0) {
visited[now*2] = visited[now]+1;
q.add(now*2);
}
}
return -1;
}
}
|
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.
