백준11048 - 이동하기 (DP) JS

https://www.acmicpc.net/problem/11048

문제에서 '미로'라고 하길래, DFS나 BFS로 풀이해야 할 줄 알았는데, 자세히 읽으니 DP 문제였다. (허허)

문제는 좌표 [0,0]위치에 있던 인물이 우향 | 우하향 | 하향 으로만 움직일 수 있고,

각 좌표마다 '사탕의 갯수'가 있다고 할 때 가장 많은 사탕을 담는 경우에 대해 묻는다.

 

따라서 특정 좌표에서 우향 | 우하향 | 하향으로 움직일 때, 움직일 좌표가 미로에서 유효한 위치인지 파악 후,

위치가 유효하다면 해당 위치의 사탕 갯수, 이전 가지고 있던 사탕의 갯수를 더해 기록(메모라이징)해나가며 풀이하면 된다.

 

전체 소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

// 유효 좌표인지 검증하는 함수
const verify = (n,m,x,y) => {
  return n > y && y >= 0 && m > x && x >= 0
}

function solution(data) {
  const [[n,m], ...matrix] = data.map(el=> el.split(' ').map(Number))
  // 메모라이징하기 위한 변수
  const dp = Array.from({length : n}, ()=> {
    return Array.from({length : m}, ()=> 0)
  })

  // 위치는 무조건 [0,0]에서 시작하므로 초깃값 설정
  dp[0][0] = matrix[0][0]

  // 순서대로 우향 | 하향 | 우하향 좌표 이동 위치를 담은 배열
  const directions = [[1,0],[0,1],[1,1]]

  // 좌표에 존재하는 [i,j]좌표를 순회한다.
  // 이떄, [i,j] 기준, '다음 이동 위치'가 유효하다면
  // 기존 메모라이징된 사탕의 수와 이번 연산으로 가져가게 될 사탕의 수를 비교하여 최댓값으로 수정한다.
  for(let i = 0 ; i < n ; i ++) {
    for(let j = 0 ; j < m ; j ++) {
      directions.forEach((el)=> {
        const [dx,dy] = el
        const [nx,ny] = [dx+j,dy+i]
        if(verify(n,m,nx,ny)) {
          dp[ny][nx] = Math.max(dp[ny][nx], dp[i][j] + matrix[ny][nx])
        }
      })
    }
  }

  console.log(dp[n-1][m-1])
}

solution(input)