DFS-미로탈출경로갯수 구하기

DFS를 사용하여 미로에서 목적지에 도달하는 경로의 갯수구하기
(BFS와 다름에 유의)

# import sys
# sys.setrecursionlimit(100000)

n, m = map(int, input().split()) #n은 row ,m은 col
maze = []
for i in range(n):
    maze.append(list(input()))


dr=[-1,0,1,0]
dc=[0,1,0,-1]
cnt=0
min=n*m
visited=[[0]*m for i in range(n)]


def dfs(row,col,cnt):
    global min
    #print(row,col,visited)
    
    if row <0 or col <0 or row >= n or col >= m:#map에서 벗어날경우 OR 벽일경우(0) return

        return
    if row==n-1 and col==m-1: #목적지 도착시
        # cnt+=1
        # print(row,col)
        if cnt<min: #가장 최소값 구하기
            min=cnt
        return 
        
   
    #else: #이동할수있는 칸이면
        #print(row,col,visited)
        #visited[row][col]=1
    for i in range(4):#상하좌우 탐색하는 부분           '상 우 하 좌'
        nr=row+dr[i]
        nc=col+dc[i]
        if nr <0 or nc <0 or nr >= n or nc >= m:
            pass
        elif visited[nr][nc]==0 and maze[nr][nc]=='1':
            visited[nr][nc]=1
            dfs(nr,nc,cnt+1)
            visited[nr][nc]=0
            #print(cnt)
            # if cnt>0:
            #     cnt+=1
            #     print(row,col)
            #     return
        

if __name__=="__main__":
    #print(maze)
    dfs(0,0,1)

    print(min)