[PS] 99클럽 코테 스터디 31일차 TIL (점프 점프)

문제

문제 링크

설명

주어진 돌다리 갯수(n) 가 주어지고 각 돌다리에 이동 값이 적혀 있다. 그 값만큼 왼쪽 또는 오른쪽으로 점프할 수 있다. 배열에 이동값을 보관했다가 이동 시 계산한다. 예를 들어, arr[i] = x 라면

• i에서 i - x로 이동할 수 있다면, 왼쪽으로 이동할 수 있고, 정점 i와 정점 i - x가 간선으로 연결된 것이다.
• i에서 i + x로 이동할 수 있다면, 오른쪽으로 이동할 수 있고, 정점 i와 정점 i + x가 간선으로 연결된 것이다.

풀이

dfs 를 시작할 지점이 입력으로 들어오고 해당 인덱스부터 왼쪽, 오른쪽을 탐색한다. 이때, 이동 후 인덱스가 배열 범위내에 있는지 확인하면서 진행한다.

public class Main {
  static int[] arr;
  static int count = 0;
  static int n;
  static boolean[] visited;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    arr = new int[n];
    visited = new boolean[n];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    int s = Integer.parseInt(br.readLine());
    dfs(s - 1);

    System.out.println(count);
  }

  private static void dfs(int index) {
    if (visited[index]) {
      return;
    }
    visited[index] = true;
    count++;
    int left = index - arr[index];
    int right = index + arr[index];

    if (isInRange(left)) {
      dfs(left);
    }
    if (isInRange(right)) {
      dfs(right);
    }
  }

  private static boolean isInRange(int index) {
    return index >= 0 && index < n;
  }
}