[python] 백준 1513 경로 찾기

https://www.acmicpc.net/problem/1513

1513번: 경로 찾기

 

 

문제 해결

• 집에서 학원을 가면서 PC방을 몇 개를 자나가는지 문제
• 지나가는 개수는 상관이 없으나 순서가 존재
• 이를 DP를 이용할지 DFS를 이용할지 생각을 해봐야한다.
• 숫자가 작아서 DFS를 사용해도 될 것 같지만 하나씩 끝까지 갔다가 다시 돌아오는 것보다 DP를 이용해 4차원(현재 행, 현재 열, 오락실 중 최대 번호, 방문한 오락실 개수)로 계산하여 한번에 경우의 수를 계산하는 것이 훨씬 빠르고 메모리도 괜찮을 것이다.

 

 

CODE

MOD = 1000007
def DP():
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1:continue
            elif board[i][j]:
                for l in range(board[i][j]):
                    for k in range(l+1):
                        dp[i][j][board[i][j]][k+1] += dp[i-1][j][l][k] + dp[i][j-1][l][k]
                        dp[i][j][board[i][j]][k+1]%=MOD
            else:
                for l in range(c+1):
                    for k in range(l+1):
                        dp[i][j][l][k] = dp[i-1][j][l][k] + dp[i][j-1][l][k]
                        dp[i][j][l][k]%MOD

def solution():
    for i in range(c+1):
        result = 0
        for j in range(c+1):
            result += dp[n][m][j][i] # x행, y열, 오락실 중 최대번호 ,방문한 오락실 개수
        result %= MOD
        print(result, end=' ')

if __name__ == '__main__':
    n, m, c = map(int, input().split())
    board = [[0 for _ in range(m+1)] for _ in range(n+1)]
    dp = [[[[0 for _ in range(c+1)] for _ in range(c+1)] for _ in range(m+1)] for _ in range(n+1)] # N행 M열 최대 PC방 인덱스 C 총 지난 PC방 개수 W
    dp[1][1][0][0] = 1
    for i in range(1,c+1):
        x, y = map(int, input().split())
        if x==1 and y==1:
            dp[1][1][0][0] = 0
            dp[1][1][i][1] = 1
        board[x][y] = i
    DP()
    solution()