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 |