스타트링크


백준 [5014] 스타트링크

문제보기
Alt text

풀이방법

  • BFS

소스코드

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;
	}
}