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;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 23757 아이들과 선물 상자 - 우선순위큐(PriorityQueue) JAVA (0) | 2024.09.17 |
---|---|
[백준] 14627 파닭파닭 - 파라매트릭서치(Paramatric Search) + 최적화 문제 결정문제로 바꿔풀기 JAVA (0) | 2024.09.16 |
[백준] 12933 오리 - 구현(Implementation) + 스택(Stack) JAVA (0) | 2024.09.16 |
[백준] 2885 초콜릿 식사 - 분할정복(DivideAndConquer) JAVA (0) | 2024.09.15 |
[백준] 1326 폴짝폴짝 - 너비우선탐색(BFS) JAVA (0) | 2024.09.14 |