https://www.acmicpc.net/problem/11048
문제
> 준규는 N×M 크기의 미로에 갇혀있다.
> 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다.
> 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.
> 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다.
> 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고,
각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.
> 또, 미로 밖으로 나갈 수는 없다.
> 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.접근
dp를 사용하여 N,M에 도착했을 때, 가장 많은 사탕을 가지는 경우를 구해준다.
i,j위치에 도달하는 방법은 문제에 주어진 세방향으로 이동하는 방법을 고려했을 때,
i-1, j에서 오는거 / i, j-1에서 오는거 / i-1, j-1에서 오는거 세가지 이다.
따라서 이 셋 중 가장 큰 수에 i,j위치에 있는 사탕의 수를 더하면 최대가 된다.
문제해결
> N과 M을 입력받고 미로를 maze[N+1][M+1]로 선언한다.
> 미로 내부의 사탕 개수를 입력받아 저장한다.
> i,j위치의 최대 사탕 개수를 구하기 위해 dp이차원 배열을 N+1,M+1크기로 선언한다.
> 앞선 i,j위치의 dp값을 구하기 위한 세방향을 따져주고 가장 큰 값에 maze[i][j]를 더해 구해준다.
>N,M위치의 사탕수인 dp를 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//11048번 이동하기
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M;
static int[][] maze;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maze = new int[N+1][M+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());
}
int[][] dp = new int[N+1][M+1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++)
dp[i][j] = maze[i][j] + Math.max(Math.max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
}
System.out.print(dp[N][M]);
}
}
후기
처음에 BFS로 풀었는데 틀렸다. 그렇게 풀면 방문처리로 인해 최대를 구해낼 수 없다고 한다.
