def mazesolve(maze): #미로 탈출의 헥심 함수

    height = len(maze) #미로의 높아 길이

    width = len(maze[0]) #미로의 너비 길이

    start = (1, 0) #미로 찾기 시작점

    end = (6, 5) #미로 찾기 끝점

    stack = [start] #미로 찾는 중 막다른 길을 탈출하기 위한 스택

    print("--------")

    maze[start[0]][start[1]] = "*" #미로 탈출의 말

    mazeprint(maze) #현재 미로 상태를 출력

    print(stack) #미로 탈출할 때의 스택 현황을 출력

    while stack: #스택이 비어 있지 않다면 계속해서 반복해서 출력하는 반복문

        current_y, current_x = stack[-1] #현재 위치는 스택의 최신 데이터

        if (current_y, current_x) == end: #현재 위치가 끝점 위치라면

            print("미로에서 탈출했습니다!") #미로를 탈출한다

            return

        moves = [(-1, 0), (0, 1), (1, 0), (0, -1)] #이동 범위 설정

        check = 0 #구분을 위한 설정값

        for move_y, move_x in moves: #이동을 위한 for문

            next_x = current_x + move_x #미리 설정된 이동 범위에 따라 현재 x, y 위치를 이동시킨다

            next_y = current_y + move_y

            #이동할 예정인 위치 좌표값이 모두 양수이고, 너비, 높이 값보다 작고, 다음 위치의 값이 0이라면

            if next_x >=0 and next_x < width and next_y >=0 and next_y < height and maze[next_y][next_x] == 0:

                stack.append((next_y, next_x)) #스택에 다음 위치 좌표를 넣기

                maze[next_y][next_x] = "*" #다음 위치의 값을 * 로 저장

                check = 1 #설정값을 1로 바꿔 X가 표시되는 것을 방지

                break

        if check == 0: #만약 다음 위치의 값이 모두 0이 아니라면(막혀있다면)

            maze[current_y][current_x] = "X" #해당 위치의 값 X로 바꾸고

            stack.pop() #스택에 저장된 해당 위치의 좌표값을 날린다

        print("--------")

        mazeprint(maze)

        print(stack)

def mazeprint(maze): #미로 출력 함수

    for y in maze:

        for x in y:

            print(x, end=' ')

        print()

# 미로 맵

maze = [

    [1, 1, 1, 1, 1, 1, 1],

    [0, 0, 0, 0, 0, 0, 1],

    [1, 0, 1, 1, 1, 0, 1],

    [1, 0, 1, 0, 1, 0, 1],

    [1, 0, 1, 0, 1, 1, 1],

    [1, 0, 0, 0, 0, 0, 1],

    [1, 1, 1, 1, 1, 0, 1]

]

print("--- 미로 ---")

mazeprint(maze)

mazesolve(maze)