BOJ5014 스타트링크

<Solution>

1. 숨바꼭질과 완전 똑같음

2. 큐에 front, back으로 인덱스 컨트롤 해주면서 front에 있는거를 Up, Down 해주면서 G 층에 간 경우를 찾기

3. Up의 경우 최대층을 넘길 수 없음

 

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ5014_스타트링크 {
	
	static int F, S, G, U, D, front = -1, back = -1;
	static int[] Q, visit, 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()); // 아래로
		Q = new int[1000001];
		visit = new int[1000001];
		d = new int[1000001];
		if(S == G)
			System.out.print(0);
		else {
			int result_n = bfs();
			if(result_n == -1)
				System.out.print("use the stairs");
			else
				System.out.print(d[back]);
		}
	}
	
	public static int bfs() {
		Q[++back] = S;
		while(front != back) {
			front++;
			// Up(최대층을 넘기면 안됨)
			if(Q[front] + U <= 1000000 && Q[front] + U >= 1 && Q[front] + U <= F) {
				if(visit[Q[front] + U] == 0) {
					Q[++back] = Q[front] + U;
					visit[Q[back]] = 1;
					d[back] = d[front] + 1;
				}
			}
			if(Q[back] == G) return 1;
			
			// down
			if(Q[front] - D <= 1000000 && Q[front] - D >= 1) {
				if(visit[Q[front] - D] == 0) {
					Q[++back] = Q[front] - D;
					visit[Q[back]] = 1;
					d[back] = d[front] + 1;
				}
			}
			if(Q[back] == G) return 1;
		}
		return -1;
	}
}