[Baekjoon] 11060_점프 점프

Silver II

문제(출처: https://www.acmicpc.net/problem/11060)

---

< 점프 점프 >

 

문제 풀이

 

bfs를 활용하며 가장 오른쪽 끝 칸으로 가기 위해 최소 몇 번 점프를 해야 하는지를 구한다.

 

 

 

 my solution (Java)

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

public class _11060_ { // 점프 점프
	static int arr[], visited[], n;
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n=Integer.parseInt(bf.readLine());
		
		arr=new int[n];
		visited=new int[n];
		st=new StringTokenizer(bf.readLine());
		
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			visited[i]=-1;
		}
		
		visited[0]=0;
		bfs(0);
		
		System.out.println(visited[n-1]);
	}
	private static void bfs(int num) {
		Queue<Integer>queue=new LinkedList<>();
		queue.add(num);
		
		while(!queue.isEmpty()) {
			int idx=queue.poll();
			int temp=arr[idx];
			for(int i=1; i<=temp; i++) {
				if(idx+i<n && (visited[idx+i]==-1 || visited[idx+i]>visited[idx]+1)) {
					visited[idx+i]=visited[idx]+1;
					queue.add(idx+i);
				}
			}
		}
	}
}

 

Main

- 미로 크기 (n) 입력

- arr : 미로 정보 저장
  visited : 최소 점프 횟수 저장

- 가장 왼쪽에서 시작하므로 visited의 0번째를 0으로 저장 및 bfs 함수 호출

- visited의 가장 오른쪽 끝 값 출력

 

bfs(시작 위치 num)

- queue에 시작 위치 추가

- queue가 빌 때까지 반복 -> 미로 칸에 쓰여 있는 수만큼 반복하여 미로 범위 안이며, 아직 방문하지 않은 곳이거나 최소 점프 수를 업데이트 가능하면 visited 값 저장 및 queue에 추가

 

---

마무리🤔

 

---