[백준] JavaScript - 이동하기 (11048)

개요

문제 이름: 이동하기 (11048)
문제 링크: https://www.acmicpc.net/problem/11048
플랫폼: 백준
알고리즘 분류: DP
소요 시간: 1시간 30분

 

문제 전문

설명

입출력

 

 

문제 풀이

해설

이 문제는 N×M 크기의 미로에서 준규가 (1, 1)에서 (N, M)까지 이동하면서 최대한 많은 사탕을 모으는 최적의 경로를 찾는 문제입니다. 동적 계획법(Dynamic Programming, DP)를 사용하여 해결할 수 있는문제입니다.

 

문제를 요약하면 다음과 같습니다.

• N x M 크기의 미로가 주어집니다.
• 각 칸에는 사탕이 일정 개수 있습니다.
• (1,1)에서 출발하여 (N,M)까지 가는데, 오른쪽, 아래, 오른쪽 아래 대각선 방향으로만 이동 가능합니다.
• 준규가 (N,M)에 도착했을 때 가져올 수 있는 사탕 개수의 최댓값을 구해야 합니다.

문제 접근 방법은 다음과 같습니다.

1. 2차원 DP 배열을 정의합니다. dp[i][j]는 (i,j)까지 왔을 때 가져올 수 있는 사탕 개수의 최댓값을 의미합니다.
2. dp[0][0]에는 (1,1) 위치의 사탕 개수를 넣어줍니다.
3. 첫번째 행 dp[0][j]는 왼쪽에서부터 오는 경우밖에 없으므로, dp[0][j] = dp[0][j-1] + candy[0][j]로 채워줍니다.
4. 첫번째 열 dp[i][0]은 위에서부터 오는 경우밖에 없으므로, dp[i][0] = dp[i-1][0] + candy[i][0]로 채워줍니다.
5. 나머지 dp[i][j]는 왼쪽(dp[i][j-1]), 위쪽(dp[i-1][j]), 왼쪽 위 대각선(dp[i-1][j-1]) 중 최댓값에 현재 위치 사탕 개수를 더한 값으로 채워줍니다.
6. 최종적으로 dp[N-1][M-1]이 (N,M)까지 왔을 때 가져올 수 있는 사탕 개수의 최댓값이 됩니다.

즉, DP를 사용하여 (1,1)부터 (N,M)까지 가는 모든 경로를 탐색하면서, 각 위치까지 올 수 있는 사탕 개수의 최댓값을 메모이제이션하는 것이 핵심입니다.

 

시도

1차 시도  (성공)

// 입력 받습니다
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 미로의 크기 N(행)과 M(열)을 추출합니다
const [N, M] = input[0].split(' ').map(Number);
// 사탕 배열을 저장할 2차원 배열을 선언합니다
const candy = [];

// 입력에서 각 행의 사탕 정보를 읽어와 candy 배열에 저장합니다
for (let i = 1; i <= N; i++) {
  candy.push(input[i].split(' ').map(Number));
}

// DP 테이블을 선언하고 0으로 초기화합니다
// dp[i][j]는 (i,j) 위치까지 이동하면서 얻을 수 있는 최대 사탕 개수를 저장합니다
const dp = Array.from(Array(N), () => Array(M).fill(0));
// 시작 위치(0,0)의 사탕을 DP 테이블에 설정합니다
dp[0][0] = candy[0][0];

// 첫 번째 행을 초기화합니다
// 첫 행에서는 왼쪽에서만 이동할 수 있으므로, 왼쪽에서 온 값에 현재 위치의 사탕을 더합니다
for (let j = 1; j < M; j++) {
  dp[0][j] = dp[0][j-1] + candy[0][j];
}

// 첫 번째 열을 초기화합니다
// 첫 열에서는 위쪽에서만 이동할 수 있으므로, 위에서 온 값에 현재 위치의 사탕을 더합니다
for (let i = 1; i < N; i++) {
  dp[i][0] = dp[i-1][0] + candy[i][0];
}

// 나머지 DP 테이블을 채워나갑니다
for (let i = 1; i < N; i++) {
  for (let j = 1; j < M; j++) {
    // 현재 위치(i,j)에 도달하는 세 가지 방법 중 최대값을 선택합니다
    // 1. 위쪽에서 아래로 이동: dp[i-1][j]
    // 2. 왼쪽에서 오른쪽으로 이동: dp[i][j-1]
    // 3. 왼쪽 위 대각선에서 이동: dp[i-1][j-1]
    // 선택한 최대값에 현재 위치의 사탕 개수를 더합니다
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i][j];
  }
}

// 목적지(N-1, M-1)에서의 최대 사탕 개수를 출력합니다
console.log(dp[N-1][M-1]);

위 코드는 다이나믹 프로그래밍을 사용하여 문제를 해결한 것입니다. 코드의 주요 내용을 설명하면 다음과 같습니다.

1. fs 모듈을 사용하여 표준 입력을 받아옵니다. 입력은 여러 줄로 주어지므로 split('\n')으로 줄 단위로 분리합니다.
2. 첫 번째 줄에서 미로의 크기 N, M을 받아옵니다. split(' ')으로 공백을 기준으로 분리하고, map(Number)로 숫자로 변환합니다.
3. 둘째 줄부터 N개의 줄에 걸쳐 각 칸의 사탕 개수를 2차원 배열 candy에 저장합니다.
4. DP 배열 dp를 N x M 크기로 초기화하고 0으로 채웁니다. dp[i][j]는 (i,j)까지 왔을 때 가져올 수 있는 사탕 개수의 최댓값을 의미합니다.
5. dp[0][0]에는 (1,1) 위치의 사탕 개수를 넣어줍니다.
6. 첫 번째 행 dp[0][j]를 왼쪽에서부터 오는 경우로 채웁니다.
   1. dp[0][j] = dp[0][j-1] + candy[0][j]로 계산합니다.
7. 첫 번째 열 dp[i][0]을 위에서부터 오는 경우로 채웁니다.
   1. dp[i][0] = dp[i-1][0] + candy[i][0]로 계산합니다.
8. 이중 for문을 사용하여 나머지 dp[i][j]를 채웁니다.
   1. dp[i][j]는 왼쪽(dp[i][j-1]), 위쪽(dp[i-1][j]), 왼쪽 위 대각선(dp[i-1][j-1]) 중 최댓값을 구합니다.
   2. 여기에 현재 위치의 사탕 개수 candy[i][j]를 더한 값이 됩니다.
9. 최종적으로 dp[N-1][M-1]이 (N,M)까지 왔을 때 가져올 수 있는 사탕 개수의 최댓값이므로 이를 출력합니다.

 

시간복잡도와 공간복잡도

• 시간복잡도: O(N * M)
  • 이중 for문을 사용하여 DP 배열을 채우므로 시간복잡도는 O(N * M)입니다.
• 공간복잡도: O(N * M)
  • N x M 크기의 DP 배열을 사용하므로 공간복잡도는 O(N * M)입니다.

 

사용된 주요 메서드

• String.prototype.trim(): 문자열 양 끝의 공백을 제거하는 메서드입니다.
• String.prototype.split(separator): 문자열을 지정한 구분자를 기준으로 분할하여 배열로 반환하는 메서드입니다.
• Array.from(arrayLike, mapFn): 유사 배열 객체나 반복 가능한 객체로부터 새로운 배열을 생성하는 메서드입니다. 두 번째 인자로 매핑 함수를 전달할 수 있습니다.
• Array.prototype.map(callback): 배열의 모든 요소에 대해 제공된 함수를 호출한 결과를 모아 새로운 배열을 반환하는 메서드입니다.
• Array.prototype.fill(value): 배열의 시작 인덱스부터 끝 인덱스까지 지정한 값으로 채우는 메서드입니다.
• Math.max(...args): 주어진 숫자 중 가장 큰 값을 반환하는 메서드입니다. 인자로 숫자들을 전달합니다.