[BOJ]11048 이동하기

이동하기

풀이

• (r+1,c),(r,c+1),(r+1,c+1) 로만 이동할 수 있으므로 bfs 풀 때처럼 dx,dy 배열 만들었음
• "각 방을 방문할 때마다 방에 놓여져 있는 사탕을 모두 가져갈 수 있다."
• "가져올 수 있는 사탕 개수의 최댓값" 을 구해라 -> dp라고 생각하고 풀었음
• 미로 2차원 배열, dp 2차원 배열을 따로 만들었고, 준규는 (1,1)에서 시작하므로 2중 for문으로 모든 칸에 대해 고려함
• 2중 for문 안에 이동할 수 있는 경우의 수 3개 돌려야 하므로 총 3중 for 문 돌림
• 내가 방문하려는 칸의 총 사탕 값(dp[nx][ny])가 내가 지금 갖고 가는 최대의 사탕값(dp[i][j])+현재 그 칸에 있는 사탕 갯수(map[nx][ny])보다 작으면 update 해줌
• dp[N-1][M-1] 출력하면 그게 답

보충

• 다른 사람 풀이를 참고해보니 대각선으로 바로 가는 값(r+1,c+1)은 항상 오른쪽이나 아래쪽으로 거쳐 가는 값보다 작다고 한다. 그래서 대각선으로 가는 방법은 고려하지 않아도 됨.

코드

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

public class Main {
    static int N,M;
    static int[][] map;
    static int[][] dp;
    static int[] dx = {1,0,1};
    static int[] dy = {0,1,1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dp = new int[N][M];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int j=0;j<M;j++){
            dp[0][j]=map[0][j];
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                for(int k=0;k<3;k++){
                    int nx = i+dx[k];
                    int ny = j+dy[k];
                    if(nx>=0 && nx<N && ny>=0 && ny<M){
                        if(dp[nx][ny]<map[nx][ny]+dp[i][j]){
                            dp[nx][ny] = map[nx][ny]+dp[i][j];
                        }
                    }
                }
            }
        }
        System.out.println(dp[N-1][M-1]);
    }
}