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

📌 오늘의 학습 키워드

[백준] 점프 점프 (Java)
https://www.acmicpc.net/problem/14248

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 첫째 줄 - 돌다리의 돌 개수 n (1 ≤ n ≤ 100,000)
둘째 줄 - 그 위치에서 점프할 수 있는 거리 Ai (1 ≤ Ai ≤ 100,000)
셋째 줄 - 출발점 s (1 ≤ s ≤ n)
출력 : 영우가 방문 가능한 돌들의 개수

가능한 시간복잡도

O(n)

알고리즘 선택

DFS

📌 코드 설계하기

1. n을 입력받아 돌들의 개수를 설정한다.
2. 돌들의 점프 거리를 stones 배열에 입력받는다.
3. 방문 여부를 확인하기 위해 visited 배열을 사용한다.
4. 현재 위치에서 시작해 가능한 모든 방향으로 이동하며, 각 위치를 방문한다.
5. 각 이동 시 이미 방문한 곳은 다시 방문하지 않도록 처리한다.
6. 방문할 수 있는 모든 위치를 탐색해 그 수를 반환한다.
7. DFS 탐색 결과, 방문할 수 있는 위치의 개수를 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Main {
    static int n;
    static int[] stones;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // n 입력
        n = sc.nextInt();
        
        // 돌들의 배열 입력
        stones = new int[n];
        for (int i = 0; i < n; i++) {
            stones[i] = sc.nextInt();
        }
        
        // 방문 확인 배열 초기화
        visited = new boolean[n];
        
        // 시작 지점 입력 및 인덱스 조정
        int start = sc.nextInt() - 1;
        
        // DFS 실행
        int result = dfs(start);
        
        // 결과 출력
        System.out.println(result);
        
        sc.close();
    }

    // DFS 함수 정의
    static int dfs(int index) {
        // 이미 방문한 곳이면 0 리턴
        if (visited[index]) {
            return 0;
        }
        
        // 현재 위치 방문 처리
        visited[index] = true;
        
        int count = 1;  // 현재 위치를 방문했으므로 1 카운트
        
        // 왼쪽 점프
        int left = index - stones[index];
        if (left >= 0) {
            count += dfs(left);
        }
        
        // 오른쪽 점프
        int right = index + stones[index];
        if (right < n) {
            count += dfs(right);
        }
        
        return count;
    }
}