[Java] 백준 14248번 : 점프 점프

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

5
1 4 2 2 1
3

예제 출력 1

5

 

소스코드

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 {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, S;
	private static int []stones;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		stones=new int[N+1];
		
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) stones[i]=Integer.parseInt(st.nextToken());
		S=Integer.parseInt(br.readLine());
		
		System.out.println(bfs(S));
	}

	private static int bfs(int x) {
		Queue<Integer> queue=new LinkedList<>();
		queue.add(x);
		
		boolean []visited=new boolean[N+1];
		visited[x]=true;
		
		while(!queue.isEmpty()) {
			int q=queue.poll();
			
			if(q-stones[q]>=1 && !visited[q-stones[q]]) {	// 왼쪽으로 이동
				visited[q-stones[q]]=true;
				queue.add(q-stones[q]);
			}
			if(q+stones[q]<=N && !visited[q+stones[q]]) {	// 오른쪽으로 이동
				visited[q+stones[q]]=true;
				queue.add(q+stones[q]);
			}
		}
		
		int cnt=0;
		for(int i=1;i<=N;i++) {
			if(visited[i]) cnt++;
		}
		return cnt;
	}
}

bfs를 이용하여 오른쪽으로 이동하는 경우와 왼쪽으로 이동하는 경우 각각에 대해 방문 가능한 모든 돌들의 개수를 구해주었습니다. 처음에 이동 횟수가 4이면 4만큼 이동하면서 밟게 되는 1~4의 모든 돌들을 방문 가능하다고 잘못 이해하여 계속 틀렸던 문제입니다. 그러나 이동 중간에 밟는 돌들은 방문 체크를 하지 않아야 합니다.