[BOJ] 5014 스타트링크

 

 

 

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int f = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int g = Integer.parseInt(st.nextToken());
		int u = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int[] distance = new int[f+1];
		Arrays.fill(distance, -1);
		Queue<Integer> q = new LinkedList<>();
		q.offer(s);
        distance[s] = 0;
		while(!q.isEmpty()) {
			int curr = q.poll();
			if(curr==g) {
				System.out.println(distance[g]);
				return;
			}
			int up = curr + u;
			if(up<=f && distance[up]==-1) {
				distance[up] = distance[curr] + 1;
				q.offer(up);
			}
			int down = curr - d;
			if(down>=1 && distance[down]==-1) {
				distance[down] = distance[curr] + 1;
				q.offer(down);
			}
		}
		System.out.println("use the stairs");
	}
}

 

시작점 0으로 하는 경우, 지나갈 때 덮을 수 있음 -> -1로 고정 후, 이미 지나간 곳은 변경되지 않도록 방지 !