HSAT 기출 7회: 순서대로 방문하기

import sys

def search(path, goal, score, answer):
    x, y = path[-1]

    if (x, y) == goal:
        if score == -m:
            answer.append(1)
        return

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        # 격자 밖으로 나감
        if not (0 < nx <= n and 0 < ny <= n):
            continue
        # 벽으로 이동
        if maps[nx][ny] == 1:
            continue
        # 중복된 경로로 이동
        if (nx, ny) in set(path):
            continue

        stage = maps[nx][ny]
        if stage < 0:
            if stage != score - 1:
                continue
            score += (-1)

        path.append((nx, ny))
        search(path, goal, score, answer)
        path.pop()
        if stage < 0:
            score -= (-1)
    return

n, m = map(int, sys.stdin.readline().split())

maps = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    lines = list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        maps[i + 1][j + 1] = lines[j]

start = end = (0, 0)
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    maps[x][y] = -(i + 1)
    if i == 0:
        start = (x, y)
    elif i == m - 1:
        end = (x, y)

answer = []
search([start], end, -1, answer)
print(sum(answer))