5014

스타트링크 : https://www.acmicpc.net/problem/5014

 

 

 

DFS : 35%에서 멈춤 -> 입력을 1000000으로 했을 때, java.lang.StackOverflowError 발생하는 것으로 보아,

채점 시에도 해당 문제가 발생했을거라 생각됨.

 

시 입력의 범위가 100만 단위가 넘어가면 dfs는 비효율적인 것 같다.

참조 : https://loosie.tistory.com/213

 

 

 

 

DFS : java.lang.StackOverflowError 

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

public class Main {

	static int F, S, G, U, D;
	static boolean[] visited;
	static long answer = Integer.MAX_VALUE;
	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());

		visited = new boolean[F + 1];
		visited[S] = true;
		dfs(S, 0);
		if( answer == Integer.MAX_VALUE)
			System.out.println("use the stairs");
		else
			System.out.println(answer);
	}

	private static void dfs(int now, int count) {
		int[] dy = { U, -D };
		if (now > F || now <= 0) {
			return;
		}
		if (now == G) {
			answer = Math.min(answer, count);			
			return;
		}

		for (int i = 0; i < 2; i++) {
			int newFlow = now + dy[i];
			if ( newFlow >= 1 && newFlow <= F && !visited[newFlow]) {
				visited[newFlow]=true;
				dfs(newFlow, count+1);
			}
		}

		return;
	}

}

 

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, S, G, U, D;
	static boolean[] visited;
	static long answer = Integer.MAX_VALUE;

	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());


		answer = bfs();
		if (answer == -1)
			System.out.println("use the stairs");
		else
			System.out.println(answer);
	}

	private static int bfs() {

		Queue<Integer> Q = new LinkedList<>();
		int[] d = { U, -D };
		int level = 0;
		visited = new boolean[F + 1];
		visited[S] = true;
		Q.offer(S);
		
		
		while (!Q.isEmpty()) {
			int size = Q.size();
			for (int q = 0; q < size; ++q) {
				int now = Q.poll();

				if (now == G)
					return level;

				for (int i = 0; i < 2; i++) {
					int next = now + d[i];
					if (next < 1 || next > F) {
						continue;
					}

					if (!visited[next]) {
						visited[next] = true;
						Q.offer(next);
					}
				}

			}
			level++;
		}

		return -1;
	}

}