백준 JAVA 14248 점프 점프 리뷰

문제풀이

돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있다

예제 입력에서 3에서 시작해서 왼쪽 or 오른쪽으로 가면 거기 돌에 또 숫자가 적혀있을 것이다.또 그만큼 이동을 하면 되고 카운트를 해주면 된다.그렇게 해서 가능한 돌 갯수를 찾으면 되고 중복을 방지하기 위해 visited 배열을 사용했다.

 

정점 방문해서 정점 개수 세는 것이 bfs dfs 문제라고 생각했다.

 

스타트링크랑 조금 비슷하다고 생각했다.

 

입력에서

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

라고 되어있는데 문제 꼼꼼히 안 읽고 입력 부분을 읽으니 두번째 줄이 무슨 말이야.. 하고 한참을 봤었다..; 

문제 파악 잘해야지.

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int[] arr;
    static boolean[] visited;
    static int count=1;
    public static void main(String[] args) throws IOException{
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        arr=new int[n+1];
        visited=new boolean[n+1];

        for(int i=1; i<=n; i++){
            arr[i]=scan.nextInt();
        }
        int s= scan.nextInt();
        bfs(s);
        System.out.println(count);
    }
    static void bfs(int s){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s]=true;

        while(!queue.isEmpty()){
            int x=queue.poll();

            if(x+arr[x]>=1&&x+arr[x]<=n&&!visited[x+arr[x]]){
                visited[x+arr[x]]=true;
                queue.add(x+arr[x]);
                count++;
            }
            if(x-arr[x]>=1&&x-arr[x]<=n&&!visited[x-arr[x]]){
                visited[x-arr[x]]=true;
                queue.add(x-arr[x]);
                count++;
            }
        }
    }
}