백준 [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, G, U, D;
static long ans;
static Queue<int[]> queue;
static boolean[] visited;
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());
int S = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
U = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
queue = new LinkedList<>();
visited = new boolean[F + 1];
ans = 987654321;
if (G == S) {
ans = 0;
} else {
queue.add(new int[] { S, 0 });
go();
}
if (ans == 987654321) {
System.out.println("use the stairs");
} else
System.out.println(ans);
}
public static void go() {
while (!queue.isEmpty()) {
int[] q = queue.poll();
if (q[1] >= ans)
continue;
// 올라갈 상황
boolean upChk = up(q);
if (!upChk)
down(q);
// 내려갈 상황
boolean downChk = down(q);
if (!downChk)
up(q);
}
}
public static boolean up(int[] q) {
boolean flag = false;
int floor = q[0] + U;
if (floor <= F &&!visited[floor]) {
if (floor == G) {
ans = Math.min(ans, q[1] + 1);
flag = true;
} else {
visited[floor] = true;
queue.add(new int[] { floor, q[1] + 1 });
flag = true;
}
}
return flag;
}
public static boolean down(int[] q) {
boolean flag = false;
int floor = q[0] - D;
if (floor >= 1 && !visited[floor]) {
if (floor == G) {
ans = Math.min(ans, q[1] + 1);
flag = true;
} else {
visited[floor] = true;
queue.add(new int[] { floor, q[1] + 1 });
flag = true;
}
}
return flag;
}
}