문제
F층 건물에서 S층에서 G층으로 이동하려 한다. 엘리베이터는 위로 U층, 아래로 D층만 이동 가능할 때, 버튼을 최소 몇 번 눌러야 하는지 구하라. 불가능하면 "use the stairs"를 출력한다.
입력
한 줄에 F, S, G, U, D가 주어진다.
출력
최소 버튼 횟수 또는 "use the stairs"를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 1 10 2 1 | 6 |
풀이
BFS로 S층에서 출발하여 G층까지의 최소 이동 횟수를 구한다.
- 시작층 S를 큐에 넣고 visited 배열로 방문 여부와 이동 횟수를 기록한다
- 현재 층에서 +U, -D 두 방향으로 이동을 시도한다
- 범위(1~F) 내이고 미방문이면 큐에 추가한다
- G층에 도달하면 이동 횟수를 출력하고, 큐가 비면 불가능이다
핵심 아이디어: 각 층을 노드, 위/아래 이동을 간선으로 보는 BFS. 가중치가 동일하므로 BFS가 최단 경로를 보장한다.
코드
package day399;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day362BOJ5014스타트링크 {
static int F, S, G, U, D, ans = -1;
static int[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
F = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
U = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
visited = new int[F + 1];
bfs();
if (ans >= 0)
System.out.println(ans);
else
System.out.println("use the stairs");
br.close();
}
private static void bfs() {
Queue<Integer> q = new LinkedList<>();
q.add(S);
visited[S] = 1;
while (!q.isEmpty()) {
int cur = q.poll();
if (cur == G) {
ans = visited[cur] - 1;
break;
}
if (cur + U <= F) {
if (visited[cur + U] == 0) {
visited[cur + U] += visited[cur] + 1;
q.add(cur + U);
}
}
if (cur - D > 0) {
if (visited[cur - D] == 0) {
visited[cur - D] += visited[cur] + 1;
q.add(cur - D);
}
}
}
}
}복잡도
- 시간: O(F) - 최대 F개 층 방문
- 공간: O(F) - visited 배열