문제
N개의 징검다리에 적힌 수의 배수만큼 양방향으로 점프할 수 있을 때, 출발점에서 도착점까지의 최소 점프 횟수를 구하라.
입력
첫째 줄에 N, 둘째 줄에 각 돌의 점프력, 셋째 줄에 출발점과 도착점이 주어진다.
출력
최소 점프 횟수를 출력한다. 불가능하면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 2 1 2 1 1 5 | 1 |
풀이
BFS로 현재 돌에서 점프력의 배수만큼 양방향으로 이동 가능한 돌을 탐색한다.
- 출발점에서 BFS를 시작한다
- 현재 돌의 점프력 k에 대해 k, 2k, 3k, ... 만큼 앞뒤로 이동 가능한 돌을 큐에 추가한다
- 방문 배열로 중복 방문을 방지한다
- 도착점에 도달하면 점프 횟수를 반환한다
핵심 아이디어: 배수 간격 점프이므로 각 돌에서 양방향으로 배수만큼 이동하는 BFS로 최단 경로를 찾는다.
코드
const solution = (input) => {
const N = +input[0];
const stones = input[1].trim().split(" ").map(Number);
const [A, B] = input[2].trim().split(" ").map(Number);
const a = A - 1;
const b = B - 1;
if (a === b) return 0;
const visited = Array(N).fill(false);
const queue = [[a, 0]];
visited[a] = true;
let head = 0;
while (head < queue.length) {
const [cur, dist] = queue[head++];
const step = stones[cur];
for (let next = cur + step; next < N; next += step) {
if (!visited[next]) {
if (next === b) return dist + 1;
visited[next] = true;
queue.push([next, dist + 1]);
}
}
for (let next = cur - step; next >= 0; next -= step) {
if (!visited[next]) {
if (next === b) return dist + 1;
visited[next] = true;
queue.push([next, dist + 1]);
}
}
}
return -1;
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(N²)
- 공간: O(N)