[프로그래머스] 등굣길

문제 이해하기

등굣길 경로의 경우의 수를 구하는 문제이다.
좌표 (1,1)인 집에서 부터 (m,n)인 학교까지 가는 경로를 구하는 문제인데 사이에 웅덩이를 피해 가야한다.

경우의 수를 계산해보면 200!/(100! * 100!)이 된다. 매우 큰 수이기 때문에 완전탐색으로는 제한시간안에 답을 찾을 수 없다.

 

 

https://m.blog.naver.com/parkhc1992/220669287080

[확률과 통계] 최단거리 경우의수

 

문제 해결 방법 설명하기

1. 최단거리 구하는 수 계산하기

최단 거리를 구하는 경우의 수는 아래의 그림과 같다. 이를 코드로 구현하면 아래와 같다.

 

def dfs(m, n, x, y, puddles, dp):
    if out_of_range(m, n, x, y) or [x, y] in puddles:
        return 0
    
    if x == m and y == n:
        return 1
    
    dp[y][x] = 0
    dp[y][x] += dfs(m, n, x + 1, y, puddles, dp) + dfs(m, n, x, y + 1, puddles, dp)
    return dp[y][x] % 1000000007

 

2. 경우의 수 기억하기

하지만 탐색 가능한 경우의 숫자가 많기 때문에 기존의 탐색한 경우의 수를 기억한 후 재탐색이 불가능하게 만들어줘야 한다.

그 방법은 아래와 같다.  이렇게 되면 모든 선분을 한번만 방문하기 때문에 최대 M *N *4가 된다. 엄밀히 말하면 이 숫자보다 더 작을 것이다.

def dfs(m, n, x, y, puddles, dp):
    if out_of_range(m, n, x, y) or [x, y] in puddles:
        return 0
    
    if x == m and y == n:
        return 1
    
    if dp[y][x] != -1:
        return dp[y][x]
    
    dp[y][x] = 0
    dp[y][x] += dfs(m, n, x + 1, y, puddles, dp) + dfs(m, n, x, y + 1, puddles, dp)
    return dp[y][x] % 1000000007

코드

def out_of_range(m, n, x, y):
    return x < 1 or x > m or y < 1 or y > n

def dfs(m, n, x, y, puddles, dp):
    if out_of_range(m, n, x, y) or [x, y] in puddles:
        return 0
    
    if x == m and y == n:
        return 1
    
    if dp[y][x] != -1:
        return dp[y][x]
    
    dp[y][x] = 0
    dp[y][x] += dfs(m, n, x + 1, y, puddles, dp) + dfs(m, n, x, y + 1, puddles, dp)
    return dp[y][x] % 1000000007

def solution(m, n, puddles):
    answer = 0
    dp = [[-1] * (102) for _ in range(102)]
    answer = dfs(m, n, 1, 1, puddles, dp)
    
    return answer

if __name__ == "__main__":
    m = 4
    n = 3  
    puddles = [[2, 2]]
    print(solution(m, n, puddles))  # 4