https://www.acmicpc.net/problem/13549
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, k;
static int answer = 0;
static boolean[] visited;
static class Point implements Comparable<Point>{
int v, cnt;
public Point(int v, int cnt) {
this.v = v;
this.cnt = cnt;
}
@Override
public int compareTo(Point o) {
return cnt - o.cnt;
}
}
static boolean check(int x) {
if (x < 0 || x > 100000 || visited[x]) return false;
return true;
}
static void bfs(int v) {
PriorityQueue<Point> queue = new PriorityQueue<>();
queue.offer(new Point(v, 0));
while (!queue.isEmpty()) {
Point p = queue.poll();
int x = p.v;
int cnt = p.cnt;
visited[x] = true;
if (x == k) {
answer = cnt;
break;
}
if (check(x-1)) {
queue.add(new Point(x - 1, cnt + 1));
}
if (check(x+1)) {
queue.add(new Point(x + 1, cnt + 1));
}
if (check(x*2)) {
queue.add(new Point(x * 2, cnt));
}
}
}
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(n);
System.out.println(answer);
/* 테스트케이스
1 2
답 0
1 17
답 1
4 6
답 1*/
}
}
헤매다가 질문 게시판에 어떤분이 올려주신 테스트케이스들을 보고 문제가 뭔지 알 수 있었다.
1 2 같은 경우에 +1로 가는 건 1초, *2로 가는건 0초가 걸린다.
그러므로 더 빨리 갈 수 있게 0초만에 갈 수 있게 해야되어서, 우선순위 큐를 만들어 cnt가 작은 값부터 우선순위를 가지도록 했다.
생각해보니까 그냥 while문안에서 *2의 경우를 먼저 작성하여 먼저 큐에 넣게 해도 됐었을거 같다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 1202번- 보석 도둑 (0) | 2023.01.16 |
---|---|
[JAVA] 백준 13305번- 주유소 (0) | 2023.01.13 |
[JAVA] 백준 13913번- 숨바꼭질 4 (0) | 2023.01.09 |
[JAVA] 백준 1697번- 숨바꼭질 (0) | 2023.01.09 |
[JAVA] 백준 1707번- 이분 그래프 (0) | 2023.01.06 |