[프로그래머스 L3] 등굣길 (javascript)

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

출처 : 프로그래머스

 

 

먼저 출발지(집)는 좌측상단에 위치하고 있고, 도착지(학교)는 우측하단에 위치하고 있기 때문에

오른쪽 & 아래쪽으로만 이동하게 되면 최단 경로로 도착할 수 있다.

 

문제 풀이에는 재귀호출 + 메모이제이션을 사용했다.

 

먼저 메모이제이션을 사용하기 위해 2차원 배열(n+1 * m+1)을 생성했다.

그리고 물에 잠긴 지역들이 담긴 배열을 돌면서, 메모이제이션 배열에 -1로 표시했다.

//메모이제이션 배열 생성
let arr = Array.from(Array(n+1), () => Array(m+1).fill(0))

//물 잠긴 지역 표시
if (puddles.length > 0) {  //빈 배열이 주어질 수도 있기에 먼저 검사 수행
    puddles.forEach(([col, row]) => arr[row][col] = -1)  //주의! 열, 행 순으로 이루어짐
}

 

 

여기서 주의할 점!

물에 잠긴 지역들이 담긴 배열 puddles의 요소들은 행, 열이 아닌 열, 행 순으로 주어진다.

예로 puddles(3,2)는 2행 3열이 물에 잠긴 지역이라는 뜻!

(테스트케이스로 (2,2)만 주어져서 금방 알아채지 못하고 한참을 헤맸다 ㅠㅠ)

 

 

그리고 매개변수 row, col 위치에서 목적지인 학교까지 접근할 수 있는 가짓수를 반환하는

getRoute라는 함수를 작성했다.

 

const getRoute = (row, col) => {
    if(row > n || col > m || arr[row][col] === -1) return 0  //벗어날 경우 or 물 잠긴 지역
    if(row === n && col === m) return 1  //도착
    if(arr[row][col] !== 0) return arr[row][col]  //메모값 있을 때
    else return arr[row][col] = (getRoute(row+1, col) + getRoute(row, col+1)) % 1000000007
}

 

1. 좌표를 벗어나거나, 물에 잠긴 지역에 접근하려 할 경우에는 0을 반환한다. (도착지에 갈 수 없으므로!)

2. 목적지(학교)에 도착했을 경우에는 1을 반환한다.

3. 메모된 값이 있을 경우(=이미 방문한 곳일 경우)에는 메모된 값을 반환한다.

4. 메모된 값이 없을 경우(=처음 방문한 곳일 경우)에는

현재 좌표의 바로 아래 좌표에서 도착지까지 접근할 수 있는 가짓수와

현재 좌표의 바로 오른쪽 좌표에서 도착지까지 접근할 수 있는 가짓수를 더한다.

그리고 이 값을 메모한다.

 

---

 

메모이제이션 배열에 저장된 값 = 현재 위치에서 학교까지 접근할 수 있는 가짓수

이 문제에서는 집에서 학교까지 가는 경우의 수를 구해야 하므로, (1,1)에 저장된 값이 정답이 된다

아래 그림들을 참고하면 이해하는데에 도움이 될 듯 하다.

 

전체 코드

function solution(m, n, puddles) {
    let arr = Array.from(Array(n+1), () => Array(m+1).fill(0))  //메모이제이션 배열
    if(puddles.length > 0) puddles.forEach(([col, row]) => arr[row][col] = -1)  //물 잠긴 지역 표시

    const getRoute = (row, col) => {
        if(row > n || col > m || arr[row][col] === -1) return 0  //벗어날 경우 or 물 잠긴 지역
        if(row === n && col === m) return 1  //도착
        if(arr[row][col] !== 0) return arr[row][col]  //메모값 있을 때
        else return arr[row][col] = (getRoute(row+1, col) + getRoute(row, col+1)) % 1000000007
    }
    
    return getRoute(1,1);
}