[JAVA] 11060번 - 점프 점프

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

두 가지 방법으로 풀었다. dp와 bfs

 

1) dp로 풀기 

dp처럼 생겨서 dp로 접근했다

문제를 매일 풀다보니 뭔가 어떤 알고리즘으로 풀어야할지 감이 생기는것 같다

 

dp[i]은 i번째까지의 최소 점프 횟수라고 생각하면 된다.

최소점프횟수니까 점화식을 만들어서 Math.min으로 비교를 해서 적은 값으로 계속 갱신을 해주면 될 것 같다.

 

이 문제는 이중반복문으로 접근해야한다.

arr배열의 값에 따라 1칸을 이동할수도 있고, 4칸,5칸을 이동할 수도 있고 비교를 해야하기때문

바깥 반복문은 1부터 n까지 돌리면서

안쪽 반복문은 1부터 arr[i]의 값까지 돌린다 

문제에서 arr[i]칸에 쓰여있는 숫자이하로 점프할 수 있다고 했기 때문

ex.arr[i]=3이면 3칸을 이동했을때, 2칸을 이동했을때, 1칸을 이동했을때 모두 최소 점프 횟수를 비교해서 값을 갱신해나가야 한다.

이걸 점화식으로 나타내면

dp[i+j] = Math.min(dp[i+j], dp[i]+1);

자기 자신의값과 dp[i]에서 한번 점프했을때 중 최소 점프 횟수를 비교해서 갱신한다.

 

 

2) bfs로 풀기

bfs로 풀 수 있는이유: 해당 인덱스에서 점프가능한 모든 경로를 시도하면서, 동시에 점프 횟수를 계산한다.

bfs는 가장 먼저 도달한 경로가 최단 경로임을 보장하기 때문에, 첫 번째로 목적지에 도달한 경로의 점프 횟수를 바로 출력하면 그것이 최소 점프 횟수

 

bfs에서 int배열을 받고, 각각 인덱스, 이동횟수를 큐에 넣어서 풀면 될 것 같다

큐에 인덱스,이동 횟수를 넣고 해당 인덱스에서 점프할 수 있는 모든 거리를 탐색

방문하지 않은 칸을 큐에 넣고, 그 칸에 도달한 경우 점프 횟수 증가시켜 저장

가장 먼저 도달한게 정답! 

 

 

 

 

시간복잡도

1) dp로 풀기

for문을 두번 돌아야한다.

O(N^2)이다 O(1,000,000)으로 1초안에 충분히 가능!

2) bfs로 풀기

 O(V+E)이다. V는 미로의 칸이다 즉 N이고, E는 점프 가능한 범위다 즉 arr[i]들의합, 최악의 경우 각 칸에서 갈 수 있는 모 든 경우를 시도하니까 O(n)

O(V + E) = O(n + n) = O(n)

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1)dp로 풀기

1. 각 숫자배열 arr과 최소점프횟수 배열 dp를 만든다

이때 arr의 크기는 n+1로 해주고(0은 안쓸거기때문)

dp의 크기는 1101이다. 왜냐하면 n이 최대 1000이고 a개 최대 100이다.

이말은 최대 arr배열이 1000까지 만들어질 수 있는데, 1000번째의 칸의 숫자가 최대100이다.

즉 1000번째 배열에서 100번째 떨어진 곳까지 점프할 수 있으니 1100칸까지 점프가 가능하다는 것이다.

그래서 +1해서 1101칸으로 dp배열을 선언한다.

 

 

2.dp배열은 최대수를 미리 넣어둔다. 왜냐면 최소값으로 갱신해야하는데 0으로 채워두면 이미 최소값이라서 안되기때문

for(int i=1; i<=n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	dp[i] = Integer.MAX_VALUE;
        }

 

3. 점화식을 바탕으로 dp배열을 채우는 반복문을 수행한다

dp[1] = 0;
        for(int i=1; i<=n; i++) {
        	if(dp[i]>=Integer.MAX_VALUE) continue;
        	for(int j=1; j<=arr[i]; j++) {
        		dp[i+j] = Math.min(dp[i+j], dp[i]+1);
        	}       	
        }

 

2) bfs로 풀기 

큐에 이렇게 배열형태로 넣을거다, 인덱스와 점프횟수다

q.add(new int[] {1,0});

 

각 칸에서 이동할 수 있는 범위를 탐색하며 bfs를 수행한다 

//현재 칸에서 점프가능한 범위 탐색 
		for(int i=1; i<=arr[x]; i++) {
			int next = x+i; //다음에 방문할 칸 계산 
			if(next <= n && !visited[next]) {
				visited[next] = true;
				q.add(new int[] {next, y+1});
			}
		}

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1) dp로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        
        int n = Integer.parseInt(br.readLine());
        int []arr = new int[n+1];
        int []dp = new int [1101];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	dp[i] = Integer.MAX_VALUE;
        }
        
        dp[1] = 0;
        for(int i=1; i<=n; i++) {
        	if(dp[i]>=Integer.MAX_VALUE) continue;
        	for(int j=1; j<=arr[i]; j++) {
        		dp[i+j] = Math.min(dp[i+j], dp[i]+1);
        	}       	
        }
        if(dp[n]>=Integer.MAX_VALUE) {
        	System.out.println(-1);
        }
        else {
        	System.out.println(dp[n]);
        }
        
        
    }  
}

 

2) bfs로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int arr[];
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());        	
        }
        
        System.out.println(bfs(n)); 
        
        
    }

private static int bfs(int n) {
	Queue<int[]>q = new LinkedList<>();
	boolean[] visited = new boolean[n+1];
	q.add(new int[] {1,0}); //시작인덱스, 이동횟수
	visited[1] = true;
	
	while(!q.isEmpty()) {
		int x = q.peek()[0]; //현재 인덱스
		int y = q.peek()[1]; //현재까지 점프 횟수 
		q.remove();
		
		if(x== n) {
			return y; //마지막 칸에 도달하면 점프 횟수 반환 
		}
		
		//현재 칸에서 점프가능한 범위 탐색 
		for(int i=1; i<=arr[x]; i++) {
			int next = x+i; //다음에 방문할 칸 계산 
			if(next <= n && !visited[next]) {
				visited[next] = true;
				q.add(new int[] {next, y+1});
			}
		}
		
	}
	return -1;
}  
}