[BOJ] 5014. 스타트링크

• 메모리 : 53,692 KB
• 시간 : 160 ms
• 코드길이 : 1,603 B
• 소요시간 : 30M
• DFS는 주어진 테케는 통과하지만 숫자가 클 경우 스택오버플로가 발생해서 런타임 에러가 발생하는 것 같다. BFS에서도 방문처리 안해도 될거라고 생각했는데 방문처리를 하지 않자 메모리 초과가 발생했다. 그래서 방문 처리한 후에도 false인 경우에만 큐에 넣도록 해야하는데 그 조건을 또 빼먹어서 메모리 초과… 나중에 뒤늦게 발견하고 추가했더니 드디어 통과! 오랜만에 풀었더니 로직은 기억해도 세부를 많이 빼먹은 것 같다. 다시 열심히 풀어야지!

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_B_5014_스타트링크 {

	static int F, S, G, U, D, ans;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.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());

		if (S == G)
			System.out.println("0");
		else if (S < G && U == 0)
			System.out.println("use the stairs");
		else if (S > G && D == 0)
			System.out.println("use the stairs");
		else {
			ans = bfs();
			System.out.println(ans == -1 ? "use the stairs" : ans);
		}
	}

	private static int bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited = new boolean[F + 1];
		queue.offer(S);
		visited[S] = true;

		int size, cur, cnt = 0, curU, curD;
		while (!queue.isEmpty()) {
			size = queue.size();
			while (--size >= 0) {
				cur = queue.poll();
				curU = cur + U;
				curD = cur - D;

				if (cur == G)
					return cnt;
				if (curU < F + 1 && !visited[curU]) {
					queue.offer(curU);
					visited[curU] = true;
				}
				if (curD > 0 && !visited[curD]) {
					queue.offer(curD);
					visited[curD] = true;
				}
			}
			cnt++;
		}
		// G층에 도착을 못한 경우이기 때문에 -1 return해준다.
		return -1;
	}

	// 런타임 에러 발생
	static int min = Integer.MAX_VALUE;
	private static void dfs(int start, int cnt) {
		if (min < cnt)
			return;

		if (start < 1 || start > F)
			return;

		if (start == G) {
			if (min > cnt)
				min = cnt;
			return;
		}

		dfs(start + U, cnt + 1);
		dfs(start - D, cnt + 1);
	}

}