백준 5014번 <스타트링크>

백준 알고리즘 5014번

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

---

5014번

스타트링크는 총 F층으로 이루어진 건물의 G층에 위치한다. 강호는 현재 S층에 있고 엘리베이터는 현재 층에서 U층 더 올라가거나 D층 내려갈 수 있다. 강호가 스타트링크에 도착하기 위해서 엘리베이터 버튼을 최소 몇 번 눌러야 하는지 구하여라.

 

입력으로 첫 줄에 F, S, G, U, D가 주어진다. 

 

출력으로 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 최솟값을 출력하면 된다. 만약 엘리베이터로 이동이 불가능하다면 "use the stairs"를 출력한다.

---

문제 해결

BFS로 풀 수 있다.

floors 배열에 각 층에 가기 위해 몇 번의 버튼을 눌러야 하는지 저장하였다. 초깃값은 모두 Integer.MAX_VALUE로 하였다.

강호의 현재 위치인 S의 floors 배열 값을 0으로 설정하고 BFS를 수행하면 된다.

 

1. 큐에 시작 위치 S를 넣는다. floors[S]는 0이다.
2. 큐에서 위치 a를 꺼낸다.
   1. continue
      1. a + U(a - D)가 1부터 F 사이의 범위가 아니라면 continue
      2. floors[a + U](floors[a - D])의 값이 floors[a] + 1보다 작거나 같다면 continue
   2. floors 배열의 값을 floors[a] + 1로 업데이트하고 큐에 위치를 넣는다.
3. BFS가 끝난 후 floors[G]값을 출력한다. 

---

코드

package bj5014;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int F = Integer.parseInt(inArr[0]);
		int S = Integer.parseInt(inArr[1]);
		int G = Integer.parseInt(inArr[2]);
		int[] UD = { Integer.parseInt(inArr[3]), -Integer.parseInt(inArr[4]) };

		int[] floors = new int[F + 1];
		for (int i = 1; i < F + 1; i++) {
			floors[i] = Integer.MAX_VALUE;
		}
		Queue<Integer> queue = new LinkedList<>();
		queue.add(S);
		floors[S] = 0;
		while (!queue.isEmpty()) {
			int a = queue.poll();
			for (int i = 0; i < 2; i++) {
				int A = a + UD[i];
				if (A > F || A <= 0) {
					continue;
				}
				if (floors[A] <= floors[a] + 1) {
					continue;
				}
				floors[A] = floors[a] + 1;
				queue.add(A);

			}

		}
		if (floors[G] == Integer.MAX_VALUE) {
			System.out.println("use the stairs");
		} else {
			System.out.println(floors[G]);
		}
	}

}

---

결과

---