[99클럽 코테 스터디 31일차 TIL] 점프 점프 - Java [자바][백준]

 

 

📜 문제 내용

 

🤔 과정

• 방문 배열과 DFS로 해결할 수 있었다. 

 

✨ 최초 제출 답안

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

public class Main {
    public static int[] bridge; // 돌다리 배열
    public static boolean[] visited; // 방문 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine()); // 돌다리 갯수
        bridge = new int[n];
        visited = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            bridge[i] = Integer.parseInt(st.nextToken());
        }
        
        int s = Integer.parseInt(br.readLine()); // 시작점

        dfs(s-1); // s번째 돌다리이므로 배열에는 -1을 해준 index 

        int cnt = 0; // 방문한 돌다리 갯수
        for(int i=0;i<n;i++){
            if(visited[i]) cnt++;
        }

        System.out.print(cnt);
        br.close();
    }// main

    public static void dfs(int curr) { // curr은 현재 위치
        visited[curr] = true; // 방문 체크 
        
        // 왼쪽으로 가면 index가 0 이상이어야하고, 미방문 돌다리일 경우
        int left = curr - bridge[curr];
        if(left >= 0 && !visited[left]){
            dfs(left);
        }

        // 오른쪽으로 가면 index가 돌다리 갯수 미만이어야하고, 미방문 돌다리일 경우
        int right = curr + bridge[curr];
        if(right < bridge.length && !visited[right]){
            dfs(right);
        }
    }
}

 

🔗 문제 링크

• 백준 - 점프 점프 (링크)