[BOJ/Java] 백준 5014번 - 스타트링크

백준 #5014 스타트링크

5014번: 스타트링크

 

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 F, S, G, U, D;

	public static void main(String[] args) throws IOException {
		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());  // 아래로 내려가는 층
		
		int[] floor = new int[F+1];  // 이동 횟수 저장
		Queue<Integer> q = new LinkedList<>();
		q.offer(S);
		floor[S] = 1;
		while (!q.isEmpty()) {
			int w = q.poll();
			if (w == G) {  // 목표 층 도착
				 break;
			}
			if (0 < w + U && w + U <= F && floor[w + U] == 0) {
				q.offer(w + U);
				floor[w + U] = floor[w] + 1;
			}
			if (0 < w - D && w - D <= F && floor[w - D] == 0) {
				q.offer(w - D);
				floor[w - D] = floor[w] + 1;
			}
		}
		
		if (floor[G] == 0) {
			System.out.println("use the stairs");
		} else {
			System.out.println(floor[G]-1);
		}
		
	}

}

 

현재 층에서 갈 수 있는 층을 Queue에 담아주며 해당 층으로 갔을 때 이동 횟수를 배열(가려는 층 인덱스)에 저장해준다. 이동 횟수는 현재 층까지 오는 데 걸렸던 이동 횟수 + 1이다. 탐색할 새로운 층을 Queue에서 뺐을 때 목표 층과 같다면 while을 빠져나와 준다.

층을 이동하는 데 조건은 건물의 총 층을 벗어나지 않고, 아직 탐색하지 않은 층이어야 한다. 탐색하지 않았는지는 이동 횟수를 저장한 배열을 통해 확인한다. 이동 횟수가 0이면 아직 탐색하지 않은 층으로 이동이 가능하다. 이때문에 처음 위치하고 있는 S층의 이동 횟수는 1로 해주고 마지막에 총 횟수를 출력할 때 총 횟수 -1 를 해주었다.