• Home

My Codegate

  • Home

백준 14248 점프 점프 자바 문제풀이

2024/01/15 Posted by Codegate Java No Comments
백준 14248 점프 점프 자바 문제풀이

문제 링크

문제 내용은 입력으로 돌다리를 받은 뒤, 마지막 입력받은 값 위치에서 시작해서, 밟고 있는 인덱스의 숫자만큼 좌우로 이동했을 경우, 최대 몇 칸을 밟을 수 있냐는 것인데

입력을 보면 무조건 한 칸은 밟을 수 있고, 이후부터 좌우로 움직여서 최대 갯수를 계산해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

  static boolean[] visited;
  static int[] map;
  static int cnt = 1;

  public static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    while (!queue.isEmpty()) {
      int poll = queue.poll();
      visited[poll] = true;

      if (poll + map[poll] < map.length) {
        if (!visited[poll + map[poll]]) {
          queue.add(poll + map[poll]);
          visited[poll + map[poll]] = true;
          cnt++;
        }
      }

      if (poll - map[poll] > -1) {
        if (!visited[poll - map[poll]]) {
          queue.add(poll - map[poll]);
          visited[poll - map[poll]] = true;
          cnt++;
        }
      }

    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int count = Integer.parseInt(br.readLine());
    map = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    visited = new boolean[count];
    bfs(Integer.parseInt(br.readLine()) - 1);
    System.out.println(cnt);
  }
}

문제는 입력값의 범위가 매우 크기 때문에 BFS를 사용해서 해결해야 하는데, Queue를 사용한 뒤 시작 위치에서 좌우로 이동할 수 있는지 확인하고, 이동 가능하다면 Queue에 추가해주면서 횟수를 더해준 후 BFS가 끝나고 나면 횟수를 출력해주면 끝이 난다.

No Comments
0

Leave a Reply Cancel Reply

Introduction

My Codegate

Latest Posts

  • Google Search Console API 연동방법
  • 인텔리제이 Gradle Dependency 최신 버전 보는 방법
  • Wallet-Tracker 개발일지
  • Moralis API 자바로 호출방법
  • IntelliJ Commit 후 Push 따로 하는 방법

Categories

  • My Project (4)
  • Java (42)
  • Algorithm (161)
    • Java (152)
    • Algorithm Knowledge (3)
    • Algorithm site usage (6)
  • Vue.js (1)
  • Spring (4)
  • Docker (2)
  • IntelliJ (20)
  • Uncategorized (7)

Recent Comments

  • Codegate on Hello world!
  • A WordPress Commenter on Hello world!

© 2025 — mycodegate.com

Prev Next