프로그래머스 등굣길

프로그래머스 Lv.3 동적 프로그래밍 문제인 등굣길 문제입니다.

 

해당 문제의 링크입니다.

코딩테스트 연습 - 등굣길

 

문제의 골자는 집에서 학교까지 가는 최단 경로의 수를 구하되, 웅덩이들이 존재하여 웅덩이를 지나지 않는 최단 경로만을 계산하는 것입니다.

 

이러한 문제는 경우의 수 합연산으로 학창 시절에 풀어본 경험이 있어, 거기서 아이디어를 얻었습니다. 해당 지점까지 최단거리로 가기 위해서는 아래나 오른쪽으로만 이동할 수 있고, 따라서 해당 지점에서 도착하는 경우의 수는 해당 지점의 위까지 도착한 경우의 수와 해당 지점의 바로 왼쪽까지 도착하는 경우의 수를 합하면 구할 수 있습니다.

 

해당 문제 풀이를 위해 작성한 코드는 다음과 같습니다.

 

 

def solution(m, n, puddles):
    board = [[0]*(m+1) for _ in range(n+1)]
    board[n-1][m] = 1
    for i in puddles:
        x, y = i
        board[y-1][x-1] = -1

    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if board[j][i] == -1:
                board[j][i] = 0
            else:
                board[j][i] = (board[j][i+1] + board[j+1][i])%1000000007
    return board[0][0]

각각의 지점에 도달하는 경우의 수를 계산하되, 저는 역으로 해당 지점에서 도착지점까지 도달할 수 있는 최단경로의 수를 계산하는 방식으로 진행하였습니다. 각각의 지점의 값을 받기 위해 board라는 2차원 배열을 설정하였고, 예외처리를 위해 가로 세로 1칸씩 더 늘려주었습니다.

또한, 도착지점에서 도착지점까지 가는 횟수를 연산 중 정상적으로 1로 계산하기 위해 1인 값을 추가하였습니다.

마지막으로, 각 웅덩이를 board에서 -1로 표기하여 이를 최단 경로 수 계산 과정에서 찾을 수 있도록 표시해두었습니다.

 

기본적인 로직은 도착지점부터 시작하여 각각의 지점에 해당 지점에서 도착지점까지 갈 수 있는 최단경로의 수를 구하는 것입니다. 최종적으로 시작지점에서 오른쪽으로 이동한 곳과 왼쪽으로 이동한 곳에서 구해진 최단경로의 수를 더하여 반환하는 형식입니다.

 

문제 조건에 값이 너무 클 경우를 대비하여 1000000007로 나눈 나머지를 return하라는 조건이 있고, m과 n이 각 열의 수와 행의 수를 나타내며 이는 puddles에서도 마찬가지로 직관적이지 못한 형태로 주어지는 것을 고려하여 문제를 해결해야 합니다.