[Softeer] 순서대로 방문하기

문제

요약

n*n 배열에서 m개의 위치를 차례대로 방문할 수 있는 경로의 개수는?

 

원본

https://softeer.ai/practice/6246

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
goals = []
for _ in range(m):
    x, y = map(int, input().split())
    goals.append((x-1, y-1))
    
answer = 0
d = [(-1,0), (1,0), (0,-1), (0,1)]
visited = [[0] * n for _ in range(n)]

def dfs(now, idx):
    global answer
    if now == goals[idx]:
        if idx == m-1:
            answer += 1
            return
        else:
            idx += 1

    x, y = now
    visited[x][y] = 1
    for dx, dy in d:
        nx, ny = x+dx, y+dy
        if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 0 and visited[nx][ny] == 0:
            dfs((nx, ny), idx)
    visited[x][y] = 0
        
dfs(goals[0], 1)
print(answer)