Level 3 등굣길 Python3

https://programmers.co.kr/learn/courses/30/lessons/42898?language=python3 

코딩테스트 연습 - 등굣길

 

최종 풀이

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_등굣길.py

hwayeon351/Programmers-Algorithms

def dp(x, y, road):
    if x < 0 or y < 0 or road[y][x] == -1:
        return 0
    if road[y][x] > 0:
        return road[y][x]
    road[y][x] = dp(x-1, y, road) + dp(x, y-1, road)
    return road[y][x]
    
def solution(m, n, puddles):
    road = [[0]*m for i in range(n)]
    for x, y in puddles:
        road[y-1][x-1] = -1
    if road[n-2][m-1] == road[n-1][m-2] == -1: return 0
    road[0][0] = 1
    return dp(m-1, n-1, road)%1000000007

---

풀이 과정

현재 위치에서 오른쪽이나 아래쪽으로 한 칸씩 이동을 하면서 학교까지 가는 최단 경로의 수를 구하는 문제이다.

가령 [1, 1]인 집에서 [2, 2]인 학교까지 도달하는 최단 경로의 수를 구해보자.

[2, 2]기준에서 왼쪽인 [1, 2]로 도달하는 경로의 수 + 위쪽인 [2, 1]로 도달하는 경로의 수 = 1 + 1 = 2이다.

또한, [1, 1]인 집에서 [3, 3]인 학교까지 도달하는 최단 경로의 수는 '[2, 3]으로 도달하는 경로의 수 + [3, 2]로 도달한느 경로의 수'이다.

 

이러한 규칙을 따라 아래와 같은 점화식을 구할 수 있다.

dp[y][x] = dp[y-1][x] + dp[y][x-1]

따라서, 학교까지 오는 최단 경로의 수를 DP 알고리즘의 top-down 방식으로 문제를 풀 수 있었다.

#top down 방식의 dp 알고리즘
def dp(x, y, road):
	#경로를 벗어났거나, 물 웅덩이인 경우 return 0
    if x < 0 or y < 0 or road[y][x] == -1:
        return 0
    #이전에 이미 road[y][x]까지의 최단 경로의 수를 구한 경우, return road[y][x] -> Memoization
    if road[y][x] > 0:
        return road[y][x]
    #road[y][x]까지의 최단 경로의 수를 모르는 경우, 왼쪽과 오른쪽 위치에 도달하는 최단 경로의 수를 더하여 구한다.
    road[y][x] = dp(x-1, y, road) + dp(x, y-1, road)
    return road[y][x]
    
def solution(m, n, puddles):
	#m x n 크기의 이차원 배열 road 초기화
    road = [[0]*m for i in range(n)]
    #물 웅덩이가 있는 곳은 -1을 할당
    for x, y in puddles:
        road[y-1][x-1] = -1
    #학교의 왼쪽과 위쪽 모두 물 웅덩이가 있다면, 학교에 도달 할 수 없으므로 return 0
    if road[n-2][m-1] == road[n-1][m-2] == -1: return 0
    #집인 road[0][0]ㅇ에 1을 할당
    road[0][0] = 1
    #학교인 road[m-1][n-1]까지 도달하는 최단 경로에 1,000,000,007을 나눈 나머지를 return
    return dp(m-1, n-1, road)%1000000007
#시간복잡도 = O(n^2) 공간복잡도 = O(n^2)

dp 알고리즘을 통해 탐색이 이뤄지는 시간복잡도는 T(4n-3+2(n-1)^2) = T(4n^2-1)이므로 O(n^2)이다.

공간복잡도는 road에서 이차원 리스트를 사용함에 따라 O(n^2)이다.