Baekjoon 14248 점프 점프 JAVA

14248번: 점프 점프

문제

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

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

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

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

조건

[입력]

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

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

 

[출력]

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

풀이

해당 문제는 전형적인 bfs 문제였고 bfs를 이용하여 쉽게 해결하였다.

먼저 입력 처리를 해준 뒤 시작점을 갱신하여 주고 나서 bfs를 돌려주면 된다.

bfs에서는 왼쪽 오른쪽에 대해서 각각 배열 범위가 벗어나는지 체크하고 벗어나지 않을 경우 이미 방문했는지를 체크해서 방문 처리 및 카운트 증가와 큐에 해당 위치를 담아주면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, arr[], ans = 1; // 시작점이 있으므로 카운트 1에서 시작
	static boolean visit[];
	static Queue<Integer> q = new LinkedList<>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[N+1];
		visit = new boolean[N+1];
		for (int i = 1; i <=N; i++) { // 입력값 처리
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int n = Integer.parseInt(br.readLine()); // 시작점 갱신
		q.add(n); // 시작점 큐에 담고 bfs 돌리기
		visit[n] = true;
		bfs();
		System.out.println(ans);
	}
	private static void bfs() {
		while(!q.isEmpty()) {
			int n = q.poll();
			if(n + arr[n] <= N && !visit[n + arr[n]]) { // 배열 범위 안이고 아직 방문안한경우
				visit[n + arr[n]] = true;
				q.add(n + arr[n]);
				ans++;
			}
			if(n-arr[n] > 0 && !visit[n - arr[n]]) {  // 배열 범위 안이고 아직 방문안한경우
				visit[n - arr[n]] = true;
				q.add(n - arr[n]);
				ans++;
			}
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드