[DFS] 미로

N * M 크기의 2차원 배열로 표현되는 미로 maze가 있다.
미로의 출발점은 maze[0][0] 이고 도착점은 maze[N - 1][M - 1]이라고 하자.
maze[i][j]의 값이 1이면 이동이 가능한 지점이고, 값이 0이면 이동이 불가한 지점이다.
미로에서의 이동은 왼쪽, 오른쪽, 위쪽, 아래쪽으로 한 칸씩만 이동이 가능하다.
출발점에서 도착점까지 이동하기 위한 최소 이동횟수를 출력하시오.
단, 탈출 경로가 없는 미로는 주어지지 않는다고 가정해도 된다.

Input
첫째 줄에 미로의 크기 N, M이 주어진다.
둘째 줄부터 N개의 줄에 M개의 0 또는 1의 값이 주어진다.
출발점과 도착점은 반드시 1로 주어지고, 출발점에서 도착점으로 이동이 가능한 경로는 반드시 하나 이상 존재한다.
4 6
1 0 0 1 1 1
1 0 1 1 0 1
1 1 0 1 1 1
0 1 1 1 0 1

7 7
1 0 1 1 1 1 1
1 1 1 0 0 0 1
0 0 0 1 1 1 1
1 1 1 1 1 0 0
1 0 0 1 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
Output
첫째 줄에 출발점에서 도착점으로 이동하는 경로의 최소 이동횟수를 출력한다.
10

26

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

# n*m크기의 2차원 미로
n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

# 4방향으로 이동 가능 -> 왼쪽, 오른쪽 위쪽, 아래쪽으로 한 칸 씩만 이동 가능
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

visited=[[0]*m for _ in range(n)]
answer=10**9
def dfs(x, y, depth, visited):
    global answer
    if x==n-1 and y==m-1: # 탈출->최소 이동횟수
        answer = min(answer, depth)
    else:
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m: #미로의 범위 안 이면
                if maze[nx][ny]==1 and visited[nx][ny]==0:
                    visited[x][y]=1 # 방문(두번 방문하지 못하게)
                    dfs(nx, ny, depth+1, visited)
                    visited[x][y]=0 # 초기화
    return answer
    

print(dfs(0, 0, 0, visited))

# 미로 탈출 경로와 모든 경우의 수 출력
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

# n*m크기의 2차원 미로
n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

# 4방향으로 이동 가능 -> 왼쪽, 오른쪽 위쪽, 아래쪽으로 한 칸 씩만 이동 가능
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

visited=[[0]*m for _ in range(n)]
answer=10**9
stack=[]
cnt=0
def dfs(x, y, depth, visited):
    global answer
    global cnt
    if x==n-1 and y==m-1: # 탈출->최소 이동횟수
        answer = min(answer, depth)
        print("-----------------------------------------")
        print(answer)
        print(stack)
        cnt+=1
        return
    else:
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m: #미로의 범위 안 이면
                if maze[nx][ny]==1 and visited[nx][ny]==0:
                    visited[x][y]=1 # 방문(두번 방문하지 못하게)
                    stack.append((x,y))
                    dfs(nx, ny, depth+1, visited)
                    visited[x][y]=0 # 초기화
                    stack.pop()
    

dfs(0, 0, 0, visited)
print("-----------------------------------------")
print("total cnt = ", cnt)