문제
수직선 위에서 N에서 K로 이동할 때 최소 시간과 그 최소 시간으로 이동하는 방법의 수를 구하라. 매 초 +1, -1, *2 중 하나를 선택한다.
입력
N과 K가 주어진다 (0 이상 100,000 이하).
출력
첫째 줄에 최소 시간, 둘째 줄에 방법의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 17 | 4 2 |
풀이
BFS로 최단 시간을 구하되, 같은 시간에 도달하는 경로의 수를 함께 세어 경우의 수를 구한다.
- 위치 N에서 BFS를 시작하며 각 위치에 도달 시간을 기록한다
- K에 처음 도달하면 최소 시간을 기록하고, 이후 같은 시간에 도달할 때마다 카운트를 증가한다
- 현재 탐색 시간이 최소 시간을 넘으면 종료한다
- 아직 미방문이거나 같은 시간에 도달 가능한 위치는 큐에 추가한다
핵심 아이디어: 일반 BFS와 달리 같은 시간에 도달하는 다른 경로도 허용해야 하므로, time[next] == time[now] + 1인 경우에도 큐에 추가한다.
코드
package day649;
import java.util.*;
import java.io.*;
class Day616BOJ12851숨바꼭질2 {
static int N, K;
static int[] time = new int[100001];
static int minTime = 987654321;
static int count = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if (N >= K) {
System.out.println((N - K) + "\n1");
return;
}
bfs();
System.out.println(minTime + "\n" + count);
}
static void bfs() {
Queue<Integer> q = new LinkedList<Integer>();
q.add(N);
time[N] = 1;
while (!q.isEmpty()) {
int now = q.poll();
if (minTime < time[now])
return;
for (int i = 0; i < 3; i++) {
int next;
if (i == 0)
next = now + 1;
else if (i == 1)
next = now - 1;
else
next = now * 2;
if (next < 0 || next > 100000)
continue;
if (next == K) {
minTime = time[now];
count++;
}
if (time[next] == 0 || time[next] == time[now] + 1) {
q.add(next);
time[next] = time[now] + 1;
}
}
}
}
}복잡도
- 시간: O(N) - N은 좌표 범위 (100,000)
- 공간: O(N)