문제
접근
수빈이의 n 값을 기준으로 걷기(- 1, + 1), 순간이동(* 2) 하면서 동생의 위치인 k와 값이 같아질 때까지 bfs를 진행하는 방법을 생각했다.
여기서 주의할 점은 걷기(- 1, + 1), 순간이동(* 2)의 소요 시간이 다르다는 것이다. 걷기는 1초의 시간, 순간이동은 0초의 시간이 걸린다.
즉, n이 k와 값이 같아지는 동안 순간이동을 많이 할 수록 짧은 시간이 걸린다는 것이다.
그렇다면, 3가지(- 1, + 1, * 2) 방법으로 이동하는 bfs를 진행할 텐데 일반적인 bfs와 어떤 차이가 있어야 할까?
다음의 예시를 보자.
입력 예시: 1 2
1에서 2를 가는 방법은 걷기(+ 1), 순간이동(* 2) 두 가지 방법이 있다. 이런 상황에서는 당연히 순간이동을 선택하는 게 정답일 것이다.
위 예시에서 볼 수 있듯, 순간이동을 걷기보다 우선 실행한다면 각 위치에서 최소 소요 시간을 구할 수 있을 것이다.
public static void bfs(int start, int[] time, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
// 순간이동 하는 경우
int nx = current * 2;
if (isRange(nx) && !visited[nx]) {
queue.add(nx);
visited[nx] = true;
time[nx] = time[current]; // 시간이 추가로 걸리지 않음
}
// 걷는 경우
for (int i = 0; i < 2; i++) {
nx = current + d[i];
if (isRange(nx) && !visited[nx]) {
queue.add(nx);
visited[nx] = true;
time[nx] = time[current] + 1; // 1초의 시간이 추가로 걸림
}
}
}
}위 코드는 필자의 풀이에서 bfs 메소드만 가져온 것이다.
while문 내부를 보면, 순간이동 하는 경우가 걷는 경우보다 먼저 실행된다.
풀이
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[] d = {-1, 1};
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[] time = new int[100001];
boolean[] visited = new boolean[100001];
bfs(n, time, visited);
System.out.println(time[k]);
}
public static void bfs(int start, int[] time, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
// 순간이동 하는 경우
int nx = current * 2;
if (isRange(nx) && !visited[nx]) {
queue.add(nx);
visited[nx] = true;
time[nx] = time[current]; // 시간이 추가로 걸리지 않음
}
// 걷는 경우
for (int i = 0; i < 2; i++) {
nx = current + d[i];
if (isRange(nx) && !visited[nx]) {
queue.add(nx);
visited[nx] = true;
time[nx] = time[current] + 1; // 1초의 시간이 추가로 걸림
}
}
}
}
public static boolean isRange(int x) {
return x >= 0 && x <= 100000;
}
}
정리
다른 풀이를 찾아보니 다익스트라 알고리즘, 우선순위 큐를 사용한 풀이가 있었다.
다익스트라 알고리즘을 사용한 풀이는 직접적인 비교가 어렵고, 우선순위 큐를 사용한 풀이와 비교해본다면 필자의 풀이는 기본 큐를 사용했기 때문에 heapify 과정이 필요하지 않다. 따라서 실행시간 측면에서 이점이 있다고 추측해볼 수 있다.
오답 처리가 되었을 때 스스로 반례를 찾았다는 것에 의의를 두고 싶다.
