백준 | 14248번. 점프 점프 | DFS, BFS

⬛ 백준 14248번. 점프 점프 | DFS, BFS

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

14248번: 점프 점프

문제

영우는 개구리다 개굴개굴개굴

영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.

영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.

현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.

입력

첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000)

다음 줄에는 출발점 s가 주어진다.(1≤s≤n)

출력

영우가 방문 가능한 돌들의 개수를 출력하시오.

---

💚나의 풀이 - DFS

• 한 번이라도 방문 가능한 돌이면 체크하고 정답++
• 방문한 곳은 다시 방문 안되도록 return 조건에 넣고
• 영우는 자기 위치에서 L로 가던가 R로 갈 수 있다
• L과 R이 각각 돌다리 범위 내에 있는 값이면서 방문 안한 돌다리이면 방문 체크 해가면서 깊이 탐색한다.
• 마지막에 방문 가능한 곳을 모두 탐색하면 복귀가 될 것이고, 방문 배열을 순회하면서 방문 체크 된 값의 개수를 answer++에 누적해서 출력하면 그것이 영우가 방문 가능한 돌들의 개수가 된다.

package to_0811_7;

import java.util.Scanner;

/*14248번. 점프 점프 */
public class Main {
	static int n;
	static boolean[] visited;
	static int[] A;//가능수
	static int s;//출발점 
	static int answer;
	//dfs
	static void DFS(int v) {
		if(visited[v]== true) return;//복귀
		
		visited[v]= true;
		
		int L = v - A[v];
		int R = v + A[v];
		
		if(L > 0 && L <= n) DFS(L);
		
		if(R >0 && R <= n) DFS(R);
	}
	
	//main
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		n = kb.nextInt();//돌다리 개수 
		A = new int[n+1];
		visited = new boolean[n+1];
	
		for(int i=1; i<=n; i++) A[i]=  kb.nextInt();
		
		s = kb.nextInt(); //출발점 
		answer = 0;
		DFS(s);
		
		//정답 출력 
		for(int i=1; i<=n; i++) {
			if(visited[i] == true) {
				answer++;
			}
		}
		System.out.println(answer);
		
	}
}