[백준] 14248 점프 점프 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색)를 활용합니다.

 

이 문제의 경우 물론 DFS로 풀 수 있습니다.

하지만, 이전에 N = 10,000 개 이상이 넘어갈시 항상 Stack 메모리 초과, 혹은 시간초과로 몇번 겪어본 경험이 있어 BFS를 사용했습니다.

일반적으로 10,000개 이상의 재귀호출의 depth 가 깊어진다고 할떄, BFS를 사용하는것이 훨씬 효과적인 것 같습니다.

코드

package Main;
 
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 N, M, P, K, A, B, X, R, T;
	static int answer = 0;
	static int[] arr = new int[100001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(st.nextToken()) - 1;
		
		System.out.println(BFS(S));
	}
	
	static int BFS(int src) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(src);
		boolean[] visited = new boolean[N];
		visited[src] = true;
		
		int cnt = 0;
		while(!q.isEmpty()) {
			int temp = q.poll();
			int dist = arr[temp];
			cnt += 1;
			for(int next : new int[]{temp + dist, temp - dist}) {
				if(next < 0 || next >=N) continue;
				if(visited[next] == true) continue;
				visited[next] = true;
				q.offer(next);
			}
			
		}
		
		return cnt;
	}
	
	
}