[알고리즘][X] 숨바꼭질 3
2024. 2. 20. 10:26ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/13549
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static boolean[] visited;
static int N;
static int K;
static StringBuilder sb = new StringBuilder();
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());
visited = new boolean[100001];
bfs(new int[] {N, 0});
System.out.println(sb);
}
// (cur[0] !=0 && K % cur[0] == 0)
private static void bfs(int[] start) {
int[] dx = {-1, 1};
Deque<int[]> deque = new ArrayDeque<>();
deque.offer(start);
visited[start[0]] = true;
while (!deque.isEmpty()) {
int[] cur = deque.poll();
if (cur[0] == K ) {
sb.append(cur[1]);
return;
}
int next = cur[0];
while (next != 0 && next * 2 <= 100000) {
next *= 2;
if (!visited[next]) {
deque.offer(new int[]{next, cur[1]});
visited[next] = true;
}
}
for (int i = 0; i < 2; i++) {
next = cur[0] + dx[i];
if (0 <= next && next <= 100000 && !visited[next]) {
deque.offer(new int[] {next, cur[1] + 1});
visited[next] = true;
}
}
}
}
}
나의 풀이
- * 2만큼 해야 하는건데 * 1, 2, 3, 4...가 되게 만들었다. 문제를 잘못 이해한 것이다.
- while의 첫번째 if문에
K % cur[0] == 0
을 넣어놨는데 이렇게 되면 2의 제곱수의 곱이 아니다. 문제를 잘못 이해한 것이다. 주의 하자!!!!
- 그리고 while문과 for문의 순서를 바꾸면 안되는데 그 이유는 2를 곱한게 무조건 depth가 작기 때문에 queue에 먼저 들어가야 하기 때문이다. 그래야 return문에서 먼저 나올 수 있다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] ⚾ (0) | 2024.02.23 |
---|---|
[알고리즘] 게리맨더링 (0) | 2024.02.22 |
[알고리즘][X] 숨바꼭질 4 (0) | 2024.02.20 |
[알고리즘][X] 숨바꼭질 2 (0) | 2024.02.19 |
[알고리즘] 캐슬 디펜스 (1) | 2024.02.16 |