[백준] code.plus(다이나믹 프로그래밍,JAVA)11060번, 점프 점프

문제 링크

11060번: 점프 점프

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

이 문제에 핵심은

1. 1×N 미로가 존재하며 각 칸마다 정수가 존재합니다.

2. 각 칸을 방문시 1~정수만큼 다음 칸으로 점프가 가능합니다.

3. 재환이는 미로 가장 왼쪽 끝에서 오른쪽 끝으로 가려할 때 최소 점프 횟수를 결과로 출력합니다.

4. 오른쪽 끝으로 갈 수 없는 경우 -1을 결과로 출력합니다.

 

저는 이 문제를 처음 접근할 때 BFS를 이용해서 풀었지만 해당 문제에 카테고리가 다이나믹 프로그래밍이기 때문에 동적계획법으로도 문제를 풀어보았습니다.

 

 

알고리즘 진행 순서.

 

BFS

 

1. 입력되는 미로의 정보를 저장합니다.

 

2. 왼쪽 끝을 시작으로 BFS탐색을 진행하여 가장 먼저 오른쪽 끝에 도달한 점프 횟수를 결과로 출력합니다.

 

 

동적 계획법

 

1. 입력되는 미로의 정보를 저장합니다.

 

2. 각 칸에서 갈 수 있는 칸을 탐색하며 가장 작은 점프 횟수를 DP에 저장합니다.

 

3. 오른쪽 끝 최소 점프 횟수가 저장된 DP[N-1]을 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력되는 미로의 정보를 저장합니다.

1

2

0

1

3

2

1

5

4

2

 

BFS

 

2. 왼쪽 끝을 시작으로 BFS탐색을 진행하여 가장 먼저 오른쪽 끝에 도달한 점프 횟수를 결과로 출력합니다.

1	2	0	1	3	2	1	5	4	2
0

 

왼쪽 끝에서 탐색 시작!

1	2	0	1	3	2	1	5	4	2
0	1

 

2번째 칸 탐색 시작!

1	2	0	1	3	2	1	5	4	2
0	1	2	2

 

탐색중....

1	2	0	1	3	2	1	5	4	2
0	1	2	2	3	4	4	4	5	5

 

먼저 도달한 점프 횟수 5를 결과로 출력합니다.경로 : 1 -> 2 -> 4 -> 5 -> 8 -> 10

 

동적 계획법

 

2. 각 칸에서 갈 수 있는 칸을 탐색하며 가장 작은 점프 횟수를 DP에 저장합니다.

1	2	0	1	3	2	1	5	4	2
0	INF	INF	INF	INF	INF	INF	INF	INF	INF

 

각 칸 탐색...

1	2	0	1	3	2	1	5	4	2
0	1	2	2	3	4	4	4	5	5

3. 오른쪽 끝 최소 점프 횟수가 저장된 DP[N-1]을 결과로 출력합니다.

 

DP[N-1] = 5을 결과로 출력한다.

 

 

BFS

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 미로에 대한 정보를 저장하였습니다.
• 왼쪽 끝 칸을 시작으로 BFS탐색을 진행하는 search 함수를 실행하였습니다.
• 최소 점프 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search는 가장 왼쪽 칸에서 각 칸에 정수에 따라 점프하는 것을 이용하여 BFS탐색하는 함수입니다.

 

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

public class Main {
    //미로 위치 관련 클래스
    static class position{
        int index, count;
        public position(int index, int count) {
            this.index = index;
            this.count = count;
        }
    }
    static int N;
    static int[] maze;	//미로 정보 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        maze = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //미로에 대한 정보 저장
        for(int i=0;i<N;i++)
            maze[i] = Integer.parseInt(st.nextToken());

        int answer = search();	//BFS탐색으로 최소 점프 횟수 저장
        bw.write(answer + "");	//최소 점프 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //미로를 BFS탐색하는 함수
    static int search(){
        Queue<position> queue = new LinkedList<>();
        boolean[] visited = new boolean[N];
        visited[0] = true;
        queue.add(new position(0, 0));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            if(cur.index == N-1)	//오른쪽 끝에 도달시.
                return cur.count;
            //점프하여 각 칸을 탐색
            for(int i=1;i<=maze[cur.index];i++){
                int tempIndex = cur.index + i;
                if(tempIndex<N && !visited[tempIndex]){
                    visited[tempIndex] = true;
                    queue.add(new position(tempIndex, cur.count + 1));
                }
            }
        }
        return -1;	//오른쪽 끝에 도달 불가능시.
    }
}

 

동적 계획법

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 미로에 대한 정보를 저장하였습니다.
• 각 칸에서 숫자만큼 점프하며 DP[]값을 저장하였습니다.
• DP[N-1]의 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

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

public class Main {
    static int N;
    static int[] maze, DP;	//미로에 대한 정보, 메모이제이션 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        maze = new int[N];
        DP = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //미로 정보 저장 및 메모이제이션 초기화
        for(int i=0;i<N;i++) {
            maze[i] = Integer.parseInt(st.nextToken());
            DP[i] = 1001;
        }
        DP[0] = 0;	//왼쪽 끝 칸에서 시작임으로 0으로 초기화
        for(int i=0;i<N-1;i++) {
            if (DP[i] == Integer.MAX_VALUE)	//해당 칸 방문 X
                continue;
            //각 칸에서 점프 가능한 칸 탐색
            for (int j = 1; j <= maze[i]; j++) {
                if(i+j<N){	//미로에 벗어나지 않을 때
                    if(DP[i+j] > DP[i]+1)	//DP를 이용해 해당 칸 최소값 구하기
                        DP[i+j] = DP[i]+1;
                }
            }
        }
        if(DP[N-1]== 1001)	//가장 오른쪽 칸 도달 불가능시.
            bw.write("-1");
        else		//가장 오른쪽 칸 도달시.
            bw.write(DP[N-1] + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}