문제

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

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

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

제한 사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

풀이

아이디어

• 그림을 그려보고 테스트 해봤는데, 일정한 규칙이 발견되었고, DP(Dynamic Programming)으로 풀어야겠다는 생각을 했다.
  • 현재위치까지 올 수 있는 방법 = 왼쪽칸까지 올 수 있는 방법의 수 + 위쪽칸까지 올 수 있는 방법의 수
• 그래서 메모이제이션 할 배열을 cache라고 생성하고, 배열 인덱스를 헷갈릴 일 없게 한 칸 씩 더 패딩을 만들어서 코드를 작성하였다.
• 집에서 시작하므로 cache[1][1] = 1로 설정하고, 물 웅덩이가 있는 곳은 -1로 초기화해주었다. 나머지는 0으로 초기화 해두었다.
• 처음에는 아래 코드와 같이 재귀로 작성했는데, 테스트는 다 맞았지만 효율성에서 다 틀렸다.

//row, col을 받아서 해당 칸을 업데이트시켜주는 함수
function recursive(cache, row, col, goalRow, goalCol) {
    let value = 0;
    //왼쪽 칸
    if(col - 1 > 0) {
        const prevCol = col - 1;
        //잠긴 지역이 아니라면
        if(cache[row][prevCol] !== -1) {
            value += cache[row][prevCol] % 1000000007;
        }
    }
    
    //위에 칸
    if(row - 1 > 0) {
        const newRow = row - 1;
        //잠긴 지역이 아니라면
        if(cache[newRow][col] !== -1) {
             value += cache[newRow][col] % 1000000007;
        }
    }
    
    cache[row][col] = value % 1000000007;
    
    const nextRow = row + 1, nextCol = col + 1;
    if(nextRow <= goalRow && cache[nextRow][col] !== -1) recursive(cache, nextRow, col, goalRow, goalCol);
    if(nextCol <= goalCol && cache[row][nextCol] !== -1) recursive(cache, row, nextCol, goalRow, goalCol);
}

function solution(m, n, puddles) {
    //인덱스를 헷갈리지 않기 위해 한칸씩 더 캐시를 만들어줌.
    const cache = Array(n+1).fill(0).map(row => Array(m+1).fill(0));
    //물에 잠긴 지역은 -1로 업데이트
    puddles.forEach(pud => {
        const [a, b] = pud;
        cache[b][a] = -1;
    })
    
    //일단 집에서부터 출발하니까 cache에서 집 위치를 1로 설정
    cache[1][1] = 1;
    
    //재귀
    if(cache[1][2] !== -1) recursive(cache, 1, 2, n, m);
    if(cache[2][1] !== -1) recursive(cache, 2, 1, n, m);
    
    //cache에서 학교 위치를 반환
    return cache[n][m] % 1000000007;
}

통과한 코드

• 재귀로 하니까 시간 초과가 많이 나서, 이중 반복문으로 접근을 바꿨더니 효율성 검증을 모두 통과하였다.
• 또한, 마지막에 cache[row][col] 값을 저장할 때 매번 1000000007로 나눠주지 않고 저장하면 효율성 검증에서 탈락하니 주의하자. (값을 항상 커지지 않게 관리해야 효율이 좋다.)

function solution(m, n, puddles) {
    //인덱스를 헷갈리지 않기 위해 한칸씩 더 캐시를 만들어줌.
    const cache = Array(n+1).fill(0).map(row => Array(m+1).fill(0));
    //물에 잠긴 지역은 -1로 업데이트
    puddles.forEach(pud => {
        const [a, b] = pud;
        cache[b][a] = -1;
    })
    
    //일단 집에서부터 출발하니까 cache에서 집 위치를 1로 설정
    cache[1][1] = 1;
    
    //row, col 순으로 반복문 중첩
    for(let row=1; row<=n; row++) {
        for(let col=1; col<=m; col++) {
            if(row == 1 && col == 1) continue;
            if(cache[row][col] == -1) continue;
            let value = 0;
            //왼쪽이 웅덩이가 아닐때
            if(cache[row][col-1] !== -1) value += cache[row][col-1]
            //위쪽이 웅덩이가 아닐때
            if(cache[row-1][col] !== -1) value += cache[row-1][col]
            
            cache[row][col] += value % 1000000007;
        }
    }
    
    //cache에서 학교 위치를 반환
    return cache[n][m] % 1000000007;
}

파이썬 코드

'''
어떤 칸에 도달하는 방법의 수 =
    윗칸에 도달하는 방법의 수 + 왼쪽칸에 도달하는 방법의 수
'''
def solution(m, n, puddles):
    BIG_NUM = 1000000007
    #m이 열, n이 행으로 표현되어있음
    row = n; col = m
    cache = [[0 for _ in range(col+1)] for _ in range(row+1)]
    #최종목적지 == cache[row][col]
    cache[1][1] = 1
    #웅덩이는 모두 -1로 표기한다
    for pm, pn in puddles:
        cache[pn][pm] = -1
    
    for i in range(1, row+1):
        for j in range(1, col+1):
            if i==1 and j==1: continue
            if cache[i][j] == -1: continue
            #위쪽이 웅덩이가 아닐 때
            if cache[i-1][j] != -1:
                cache[i][j] += cache[i-1][j] % BIG_NUM
            #왼쪽이 웅덩이가 아닐 때
            if cache[i][j-1] != -1:
                cache[i][j] += cache[i][j-1] % BIG_NUM
    
    return cache[row][col] % BIG_NUM