[softeer] lv3 순서대로 방문하기_python

탐색인데 조건이 있으니 백트래킹.
타겟으로 주어진 좌표를 순서대로 지나치며 마지막 도착지까지 가는 가짓수를 구하면 된다.
방문한 곳은 재방문 불가니까 visit 생성.
재귀로 풀었다.
가장 기본적인 문제. 생각한다고 좀 골아팠다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(n)]
visit = [[False]*n for _ in range(n)]
target = []
for _ in range(m):
    y, x = map(int, input().split())
    target.append([y-1,x-1])

dy, dx = [0, -1, 0, 1], [-1, 0, 1, 0]
count = 0
def backtrack(y, x, cnt):
    global count
    if cnt == m:
        count += 1
        return
    
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < n and 0 <= nx < n and not visit[ny][nx] and not ground[ny][nx]:
            visit[ny][nx] = True
            if [ny, nx] == target[cnt]:
                backtrack(ny, nx, cnt+1)
            else:
                backtrack(ny, nx, cnt)
            visit[ny][nx] = False
for y in range(n):
    for x in range(n):
        if not ground[y][x]:
            visit[y][x] = True
            if [y,x] == target[0]:
                backtrack(y, x, 1)
            visit[y][x] = False
print(count)