백준 11060 - 점프 점프

Java

11060 번 - 점프 점프

문제

접근 방법

BFS로 해결 시, 처음 도달하는 위치가 최단거리(최소비용)으로 도달하였다고 생각한다.
따라서 Boolean 방문여부 체크 배열을 통해 마지막 위치에 처음 도달하였을 때, 점프 회수를 구한다.

DP로 해결 시, dp[i]를 점프해야 하는 최소 횟수로 정의한다. dp[i]의 최소 횟수와 그 이후 들어온 횟수를 비교해서 min 값을 저장

코드 - BFS

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[] map;
	static boolean[] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	map = new int[n + 1];
    	vis = new boolean[n + 1];

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		map[i] = stoi(stk.nextToken());
    	}
    	result = Integer.MAX_VALUE;

    	BFS();
    	if(result == Integer.MAX_VALUE) {
    		System.out.println(-1);
    	}
    	else {
    		System.out.println(result);
    	}


    	br.close();
	}

	static void BFS() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {0,0});
		vis[0] = true;

		int[] q;
		int curN, val, nextN, cnt;
		while(!queue.isEmpty()) {
			q = queue.poll();
			curN = q[0];
			cnt = q[1];
			val = map[curN];

			// 종료 조건
			if(curN == n - 1) {
				result = cnt;
				return;
			}
			for(int i = 1; i <= val; i++) {
				nextN = curN + i;
				if(nextN < n && !vis[nextN]) {
					vis[nextN] = true;
					queue.add(new int[] {nextN, cnt + 1});
				}
			}
		}
	}


	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

코드 - DP

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[] dp, map;
	static final int MAX = 987654321;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	dp = new int[n + 1];		// 해당 인덱스까지 도달하는데 걸리는 최소 점프 수
    	map = new int[n + 1];

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		map[i] = stoi(stk.nextToken());
    	}
    	Arrays.fill(dp, MAX);
    	dp[0] = 0;
    	for(int i = 0; i < n; i++) {
    		for(int j = 1; j <= map[i]; j++) {
    			if(i + j < n) {
    				dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
    			}
    		}
    	}

    	if(dp[n - 1] == MAX) {
    		System.out.println(-1);
    	}
    	else {
    		System.out.println(dp[n - 1]);
    	}


    	br.close();
	}



	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점