10164 격자상의 경로 [python]

k 포인트 기준으로 두개의 영역으로 나눠 그 경우의수를 곱하는 방식을 이용하였다.

메모제이션을 사용하지않고 완전탐색을 하면 15x15 크기여도 시간초과로 인해 풀 수가 없다.

각 이동경로마다 방문된 곳이면 방문하지않고 방문된곳의 크기를 올리는 방식으로 문제를 풀었다

방문하는방법은 bfs를 이용하였다.

def bfs(sy, sx, ey, ex):
    direct = [[0, 1], [1, 0]]

    q = [(sy, sx)]
    matrix[sy][sx] = 1

    while q:
        y, x = q.pop(0)
        for dy, dx in direct:
            cy = dy + y
            cx = dx + x
            if cy >= ey + 1 or cx >= ex + 1:
                continue
            if matrix[cy][cx]:
                matrix[cy][cx] += matrix[y][x]
            else:
                matrix[cy][cx] += matrix[y][x]
                q.append((cy, cx))
    return matrix[ey][ex]


n, m, k = map(int, input().split())
matrix = [[0] * m for j in range(n)]

if k == 0:
    ky, kx = 0, 0
else:
    k -= 1
    ky, kx = k // m, k % m

print(bfs(0, 0, ky, kx) * bfs(ky, kx, n - 1, m - 1))