🔥[99클럽 코테 스터디] 31일차 TIL - 점프 점프

⏳문제

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

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

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

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

입력

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

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

출력

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

📃입출력 예

예제 입력

5
1 4 2 2 1
3

예제 출력

5

---

✏️풀이

🐸나의 풀이

나는 배열과 인덱스를 잘 활용하면 문제를 풀 수 있겠다는 생각이 들었다.

영우가 밟고 있는 돌에 적혀 있는 숫자만큼 좌, 우로 이동할 수 있다고 했기 때문에,
현재 영우가 밟고 있는 돌의 인덱스에 돌에 적혀 있는 숫자를 더하고 빼줌으로써, 좌우로 이동하는 걸 구현할 수 있었다.

이동 후 같은 매커니즘으로 돌다리를 반복해서 건너가야 하기 때문에, 이를 재귀 함수로 만들어 호출해보기로 했다.
단, 점프를 할 수 있는 조건은 점프한 후 돌의 번호가 돌다리의 범위 내에 있어야 하고, 해당 돌을 방문한 적이 없어야 한다.

🐸나의 코드

import java.util.*;

public class Main {
    public static int[] stones; // 돌다리 정보
    public static int count; // 돌 개수
    public static ArrayList<Integer> visited = new ArrayList<>(); // 돌 방문 여부

    // 점프 메서드
    public static void step(int start) {
        // start가 돌다리 범위 내에 있고, 방문하지 않은 경우에만 이동
        if (start > 0 && start <= count && !visited.contains(start)) {
            visited.add(start); // 방문한 돌 저장
            step(start - stones[start]); // 왼쪽으로 점프
            step(start + stones[start]); // 오른쪽으로 점프
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        count = sc.nextInt();
        stones = new int[count + 1];

        // 돌 정보 입력
        for (int i = 1; i <= count; i++) {
            stones[i] = sc.nextInt();
        }

        // 출발지 입력
        int start = sc.nextInt();

        // 점프
        step(start);

        // 방문한 돌 개수 출력
        System.out.println(visited.size());
        
        sc.close();
    } 
}

🐸코드 설명

1. 먼저 돌의 개수를 입력받고, 해당 개수만큼의 돌 정보를 입력받아 stones배열에 저장한다.

2. 출발지를 입력받고, step함수를 호출한다.

3. start가 돌다리 범위 내에 있고, 방문한 적이 없다면,

4. 방문한 돌을 visited 리스트에 저장한다.

5. 현재 위치(start)에서 해당 돌에 적혀 있는 숫자를 뺀 값을 가지고 step함수를 재귀 호출한다. (왼쪽으로 점프)

6. 현재 위치(start)에서 해당 돌에 적혀 있는 숫자를 더한 값을 가지고 step함수를 재귀 호출한다. (오른쪽으로 점프)

---

🔗문제 링크
💻Repository