[JS] 프로그래머스_level 3_등굣길

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

 

풀이

해당 문제를 풀이할 때 처음에는 DFS 접근법을 조합으로 생각했지만, 구현하다 보니 DFS보다는 DP로 접근해 각 구역에 도착할 수 있는 가지수를 저장해 사용하는 것이 더 좋다고 생각해 DP를 사용하기로 했다.

 

DP를 사용해 현위치에서 이전위치(상, 좌 위치에 있는) 값을 현제 위치에 더해준다. 이런 방법에서 중요한 부분은 조건처리이다. 이전 위치가 지도를 벗어나거나 물웅덩이라면 0을 더해준다.

 

24.11.12 추가 풀이 진행

이 문제에서의 핵심은 "최단 거리"이다. 목표지점은 항상 2차원 배열의 마지막 요소이며, 이 지점까지 최단거리로 도달하려면 오직 "아래"와 "오른쪽" 방향으로만 이동해 도달해야 한다.

 

그렇다면 현제 노드에 도달할 수 있는 방법은 위와 왼쪽의 노드로 부터의 접근이 가능하다는 것이다. 두 방향에서 올 수 있기 때문에 두 방향의 접근 개수를 더해 저장하면 해당 칸에 도달할 수 있는 최단 경로의 개수가 나온다.

 

코드

function solution(m, n, puddles) {
  const map = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));
  puddles.forEach(([y, x]) => {
    map[x - 1][y - 1] = -1;
  });
    
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (i === 0 && j === 0) {
        map[i][j] = 1;
      }
      else if (map[i][j] >= 0) {
        const up = (i > 0 && i < n && map[i - 1][j] > 0) ? map[i - 1][j] : 0;
        const left = (j > 0 && j < m && map[i][j - 1] > 0) ? map[i][j - 1] : 0;
        map[i][j] += (up + left) % 1000000007;
      }
    }
  }
    
  return map[n - 1][m - 1];
}