백준 10164번 : 격자상의 경로 in Python

10164번: 격자상의 경로

 

www.acmicpc.net

이 문제는 N*M의 격자에서 맨 왼쪽 위 칸에서 출발해 맨 오른쪽 아래 칸까지 가는 서로 다른 경로의 수를 구하는 문제이나 중간에 반드시 경유해야 하는 칸이 주어질 수도 있다.

이를 해결하기 위해서는 각 칸에 대해 그 칸까지 도달하기 위한 경로의 수를 저장하는 배열을 만든다. 그리고 맨 왼쪽 위 칸부터 시작해 각 칸마다 경로의 수를 순차적으로 구하는데, 임의의 칸까지 도달하기 위한 경로의 수는 그 칸의 바로 위 칸까지 가기 위한 경로의 수와 바로 왼쪽 칸까지 가기 위한 경로의 수를 더해서 구한다. 왜냐하면 이동 방향이 항상 오른쪽 또는 아래쪽이기 때문이다. 

이때 만약 반드시 경유해야 하는 칸이 있을 경우, 첫 칸에서 시작해 경유해야 하는 칸까지 가는 경로의 수와, 경유하는 칸에서 시작해 마지막 칸까지 가는 경로의 수를 곱해서 구한다.

이를 코드로 구현하면 다음과 같다.

N, M, K = map(int, input().split())
# start 칸에서 시작해 end 칸까지 가는 경로의 수를 반환하는 함수
def dp(start, end):
    global N
    global M
    mat = [[0]*(M) for _ in range(N)]
    # start, end 칸이 행렬 상에서 어느 위치인지를 구한다.
    start_row = start//M
    start_col = start%M
    end_row = end//M
    end_col = end%M
    # 초기값으로 start 칸까지 가는 경로의 수를 1로 지정한다.
    mat[start_row][start_col] = 1
    for i in range(end_row+1):
        for j in range(end_col+1):
            # 맨 윗줄에서는 오른쪽 방향으로만 이동할 수 있다.
            if i == 0 and j > 0: mat[i][j] += mat[i][j-1]
            # 맨 왼쪽줄에 있는 칸은 아래쪽 방향으로만 이동해서 도달할 수 있다.
            elif i > 0 and j == 0: mat[i][j] += mat[i-1][j]
            elif i > 0 and j > 0: mat[i][j] += mat[i-1][j] + mat[i][j-1]
    return mat[end_row][end_col]
if K == 0:
    print(dp(0, N*M-1))
else:
    print(dp(0, K-1)*dp(K-1, N*M-1))