
https://www.acmicpc.net/problem/13549
문제분석
이 문제는 다음과 같은 이동을 합니다:
x - 1
x + 1
x * 2
즉, 간선 가중치가 0 또는 1 입니다.일반 BFS는 모든 간선 가중치가 동일할 때만 최단거리를 보장합니다. 따라서 이 문제는 0-1 BFS로 풀어야 합니다.
int[] dist = new int[100_001];
dist[x]의 의미는:시작점 N에서 x까지 가는 최소 시간 입니다.
자바에서 int 배열은 기본값이 0입니다.하지만 우리는 이런 비교를 합니다: if(dist[next] > 새 거리) 따라서 초기값을 반드시 무한대로 설정해야 합니다. 따라서 Deque를 사용합니다.
0 앞 (offerFirst)
1 뒤 (offerLast)
이렇게 하면 큐 내부가 자동으로 거리 기준 정렬 상태를 유지합니다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken()); // 목적지
int[] dist = new int[100_001]; // idx 칸에 가는 데 걸리는 시간 최소값
Arrays.fill(dist, Integer.MAX_VALUE); // 0-1 BFS이므로, 시간비교를 위해 최대값으로 초기화
ArrayDeque<Integer> q = new ArrayDeque<>();
q.offer(N);
dist[N] = 0;
while(true){
int cur = q.poll();
if(cur == K){
System.out.println(dist[cur]);
return;
}
// +1이랑 -1은 시간 1초 추가해야 함
int[] nArr = {cur + 1, cur - 1};
for(int n : nArr){
if(n >= 0 && n <= 100_000 && dist[n] > dist[cur] + 1){ // cur + 1초 보다 n가는게 더 걸리면, cur에서 1초 써서 n 가는게 더 빠르니 업데이트
dist[n] = dist[cur] + 1;
q.offer(n);
}
}
// *2는 시간 소모 안함
if(cur * 2 <= 100_000 && cur * 2 >= 0 && dist[cur * 2] > dist[cur]){
dist[cur * 2] = dist[cur];
q.offerFirst(cur * 2);
}
}
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1029 그림 교환 (0) | 2026.03.05 |
|---|---|
| [JAVA] 백준 1260 DFS와 BFS (0) | 2026.03.03 |
| [JAVA] 백준 9935 문자열 폭발 (0) | 2026.02.28 |
| [JAVA] 백준 3078 좋은 친구 (0) | 2026.02.28 |
| [JAVA] 백준 3078 좋은 친구 (0) | 2026.02.27 |