백준 14248번 점프 점프 (java)

[Silver II] 점프 점프 - 14248

문제 링크

성능 요약

메모리: 33164 KB, 시간: 260 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 12일 23:42:04

문제 설명

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

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

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

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

입력

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

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

출력

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

풀이

문제 설명이 좀 이상하다

개구리가 왼쪽이나 오른쪽 둘 중 하나로만 점프할 수 있고 그 때 방문한 돌 개수를 출력하라고 하는데,

 

이 문제를 풀려면 처음 시작점에서 왼쪽으로 점프했을 때 모든 경우 + 오른쪽으로 점프했을 때 모든 경우

 

를 출력해야 정답으로 인정이 된다.

 

당연히 왼쪽으로 점프하거나 오른쪽으로 점프했을 때 최댓값을 구하는 거겠거니 생각을 했는데

 

문제 설명에서 제시한 전제를 그냥 무시해버리고 설명도 없다.

 

풀이는 간단하다.

 

돌판에 써있는 숫자를 기준으로 간선을 받은 후, 간선에 따라 노드를 돌아다니며 방문한 노드의 개수만 출력해주면 끝이다.

 

전체 코드

public class Main {

    static int N, start = 0;
    static boolean visited[];
    static List<ArrayList<Integer>> edge = new ArrayList<>();

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        for(int  i = 0 ;i<=N;i++){
            edge.add(new ArrayList<Integer>());
        }

        visited = new boolean[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i =1;i<=N;i++){
            int a = Integer.parseInt(st.nextToken());

            if((i - a) > 0){
                edge.get(i).add(i-a);
            }
            if((i+a) <= N){
                edge.get(i).add(i+a);
            }
        }

        start = Integer.parseInt(br.readLine());
        visited[start] = true;

        dfs(start);

        int cnt = 0;

        for (boolean b : visited) {
            if(b){
                cnt++;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

    public static void dfs(int now) {
        while(!edge.get(now).isEmpty()){
            int re = edge.get(now).get(0);
            if(!visited[re]){
                visited[re] = true;
                dfs(re);
            }
            edge.get(now).remove(0);
        }
    }



}