백준 [10164] 격자상의 경로 (Python3)

문제 링크 : https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

완전 탐색

BFS를 통해 격자까지 가는 경우의 수 * 격자에서 N * M 번 수가 있는 곳까지 가는 경우의 수를 곱한다.

N크기가 작았기 때문에 AC를 받을 거라 생각했지만, 부분점수만 맞았다.

 

이유를 생각해보니 경우의 수를 세야 하기 때문에 이전에 갔던 곳을 또 갈 수 있다.
즉, 방문 처리를 하지 못하기 때문에 N, M이 커질 수록 탐색 횟수도 급증했다.

 

이 문제를 해결하기 위해 이전에 탐색한 곳에 대한 정보를 가지고 있을 필요가 있었다.

 

완전 탐색 최적화 - DP

처음 봤을 때, 격자 + 탐색이길래 그래프 탐색인줄 알고 바로 bfs 돌렸다가 테케 2까지 맞았다.

 

탐색의 방향이 오른쪽, 아래 총 2개이기 때문에 한 인덱스를 기준으로
해당 위치의 바로 위, 왼쪽의 경우의 수 합이 현재 위치로 갈 수 있는 경우의 수가 된다.

 

1번 칸부터 K까지 가는 경우의 수와 K의 위치부터 N * M번까지 가는 경우의 수를 곱한다.

 

K > 0인 경우, 처음부터 다시 경우의 수를 구해야 하기 때문에 기존 경우의 수 값은 초기화 한다.
나는 N, M의 최대가 15이기 때문에 2번 순회하는 식으로 했다.

 

코드

N, M, K = map(int, input().split())

def dp(startY, startX, endY, endX):
    board = [[0 for _ in range(M)] for _ in range(N)]
    for i in range(startY, N):
        for j in range(startX, M):
            board[i][j] += board[i - 1][j] + board[i][j - 1]
            if board[i][j] == 0:
                board[i][j] = 1
    return board[endY][endX]

ans = 1
ky, kx = 0, 0
if K != 0:
    ky, kx = (K - 1) // M, (K - 1) % M
    ans *= dp(0, 0, ky, kx)
ans *= dp(ky, kx, N - 1, M - 1)
print(ans)