[백준] code.plus(다이나믹 프로그래밍,JAVA)11048번, 이동하기

문제 링크

11048번: 이동하기

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

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

이 문제에 핵심은

1. N×M 미로가 존재하며 각 칸마다 캔디가 존재합니다.

2. 각 칸을 방문할 때 해당 칸에 있는 캔디를 모두 가져갑니다.

3. 준규는 →, ↓, ↘으로만 이동할 수 있습니다.

4. 준규는 (0, 0)에서 출발해서 (N-1, M-1)을 도착할 때 가질 수 있는 최대 캔디 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. (0, 0)을 기준으로 →, ↓으로 이동하면서 최소값들을 DP의 저장합니다.

 

점화식 : DP[i][j] = Math.max(maze[i][j] + DP[i-1][j], maze[i][j] + DP[i][j-1])

 

maze[i][j] + DP[i-1][j] = ↓으로 해당 칸에 도착했을 때

maze[i][j] + DP[i][j-1] = →으로 해당 칸에 도착했을 때

 

※↘의 방향은 탐색하지 않는 이유는 (→↓), (↓→)의 순으로 이동하는 것보다 절대 캔디의 수가 클 수 없기 때문입니다.

Ex.

2	2	5
1	2	0
5	0	3

 

(0,0)에서 ↘으로 이동하면 가질 수 있는 캔디는 4개

(0,0)에서 (→↓)으로 이동하면 가질 수 있는 캔디는 6개

(0,0)에서 (↓→)으로 이동하면 가질 수 있는 캔디는 5개

 

(1,1)에서 ↘으로 이동하면 가질 수 있는 캔디는 5개

(1,1)에서 (→↓)으로 이동하면 가질 수 있는 캔디는 5개

(1,1)에서 (↓→)으로 이동하면 가질 수 있는 캔디는 5개

 

↘으로 이동해서 얻는 캔디 수는 (→↓), (↓→)의 순으로 이동하는 것보다 절대 캔디의 수가 클 수 없다.

 

3. 모든 이동이 끝난뒤 DP[N-1][M-1]을 결과로 출력합니다.

 

 

 

예제입력 1.

 

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

1	2	3	4
0	0	0	5
9	8	7	6

 

2. (0, 0)을 기준으로 →, ↓으로 이동하면서 최소값들을 DP의 저장합니다.

 

DP[0][0] = 1

DP[1][0] = 1

DP[0][1] = 3

1	3
1	DP[1][1]

 DP[1][1] = Math.max(0 + 1, 0 + 3) = 3

....

1	3	6	10
1	3	6	15
10	18	25	31

 

 

3. 모든 이동이 끝난뒤 DP[N-1][M-1]을 결과로 출력합니다.

 

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

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 미로에 대한 정보를 저장하였습니다.
• 2중 for문을 통해서 (0, 0)을 기준으로 →, ↓이동하며 DP[][]값을 저장하였습니다.
• DP[N-1][M-1]의 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main {
    static int N,M;
    static int[][] maze;	//미로 정보 저장 배열
    static int[][] DP;		//메모이제이션 배열
    static int[] dx = {1, 0};	//→, ↓에 대한 x변경값
    static int[] dy = {0, 1};	//→, ↓에 대한 y변경값
    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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new int[N+1][M+1];
        DP = new int[N+1][M+1];
        //1. 입력되는 연구소의 정보를 저장합니다.
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=M;j++){
                maze[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //2. (0, 0)을 기준으로 →, ↓으로 이동하면서 최소값들을 DP의 저장합니다.
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                DP[i][j] = Math.max(maze[i][j] + DP[i-1][j], maze[i][j] + DP[i][j-1]);
            }
        }
        //3. 모든 이동이 끝난뒤 DP[N-1][M-1]을 결과로 출력합니다.
        bw.write(DP[N][M] + "");
        bw.flush();
        bw.close();
        br.close();
    }
}