[프로그래머스] 등굣길 - python

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

코딩테스트 연습 - 등굣길

---

문제설명

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

입출력 예 설명

 

 

문제접근 - 동적계획법

문제에서 말하는 최단경로는 웅덩이를 피해 갈 수 있는 최단경로가 아니라,

절대적인 최단경로이다. 웅덩이를 피해 가는 경우는 고려해서는 안되며,

우측하단까지 가는 가능한 직선거리의 갯수만 구하면 된다.

따라서 좌측이나 위로 꺾어서 가는 경우는 고려하지 않아도 된다.

 

오른쪽과 아래로만 가게 될 경우 집에서 각 칸까지의 최단경로 경우의 수 D[i][j]는

다음의 점화식을 가지게 된다.

D[i][j] = D[i-1][j] + D[i][j-1]

 

n x m 배열을 선언하고, 시작지점  (1,1)은 1로 초기화한 후(기저사례)

(1,1)에서 각 지점 (i,j) 까지의 최단경로 경우의 수를 점화식에 따라 계산해 board[i][j]에 저장했다.

 

 

소스코드

'''
    동적계획법을 사용해 풀었습니다.
    n x m 배열(board)을 만들고, 배열의 값을 집(1,1)에서 각 위치까지의 최단경로의 경우의 수를 저장하고,
    목적지인덱스에 담긴 값(board[n][m])을 반환했습니다.
'''
 
def is_possible(row, col, board):
    """ board[row][col]이 웅덩이인지 확인. """
 
    return True if board[row][col] > -1 else False
 
 
def calc_number_of_case(row, col, board):
    """ board[row][col]에서의 최단경로 경우의 수 계산. """
 
    if is_possible(row, col-1, board):
        board[row][col] += board[row][col-1]
    if is_possible(row-1, col, board):
        board[row][col] += board[row-1][col]
    return
 
 
def set_board(m, n, board, puddles):
    """ 지도 세팅. """
 
    for i in range(1, n+1):
        for j in range(1, m+1):
            if [j, i] in puddles:
                board[i][j] = -1
            else:
                board[i][j] = 0
 
 
def solution(m, n, puddles):
    """ 배열을 순회하며 각 집(1,1)에서 각 지점까지의 최단경로 경우의 수를 갱신. """
    board = [[-1] * (m+2) for _ in range(n+2)]
 
    set_board(m, n, board, puddles)
 
    board[1][1] = 1
 
    for i in range(1, n+1):
        for j in range(1, m+1):
            if not is_possible(i, j, board):
                continue
            calc_number_of_case(i, j, board)
 
    # 목적지의 최단경로값 반환
    return board[n][m] % 1000000007
 
 
def main():
 
    m, n = 4, 3
    puddles = [[1, 3], [3, 1]]
 
    print(solution(m, n, puddles))
 
 
if __name__ == '__main__':
    main()