• Home

My Codegate

  • Home

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

2024/01/15 Posted by Codegate Java No Comments

문제 링크

문제를 보면 입력으로 숫자 배열을 받은 뒤, 현재 위치한 숫자 기준으로 오른쪽에 숫자 칸 만큼 이동할 수 있는데 배열의 끝까지 가는데 성공하면

움직인 횟수를 출력하고, 끝까지 가지 못했을 경우에는 -1을 출력해주면 끝이다

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 int[] map;
  static boolean[] visited;
  static int ans = -1;

  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[map.length];
    bfs(0);
    System.out.println(ans);
  }

  public static void bfs(int start) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{start, 0});
    while (!queue.isEmpty()) {
      int[] poll = queue.poll();
      visited[poll[0]] = true;
      if (poll[0] == map.length - 1) {
        if (ans == -1) {
          ans = poll[1];
        } else {
          ans = Math.min(ans, poll[1]);
        }
        break;
      }
      for (int i = 1; i <= map[poll[0]]; i++) {
        if (poll[0] + i < map.length) {
          if (!visited[poll[0] + i]) {
            queue.add(new int[]{poll[0] + i, poll[1] + 1});
            visited[poll[0] + i] = true;
          }
        }
      }
    }
  }
}

움직이는 경우의 수가 굉장히 많기 때문에 BFS를 사용해줘야 하는데, Queue에 이동할 수 있는 칸과 이동 칸수를 넣어 계속 이동시키면서, visited 배열을 사용해서 동일한 칸은 다시 방문하지 않도록 하고

Queue로 경우의 수를 모두 확인하다가 끝에 도달하면, 가장 작은 값만 갱신시키는 식으로 최소 횟수를 찾아 출력해주면 끝이다.

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