[자료구조] 스택 - 미로 탐색

728x90

 

 

 

🙆‍♂️ 미로 탐색 (깊이 우선 탐색) 알고리즘

---

"""
깊이우선탐색 - 미로 탐색
"""

#미로 정의
maze = [[1,1,1,1,1,1],
      ['H',0,0,0,0,1],
      [1,0,1,0,1,1],
      [1,1,1,0,0,'X'],
      [1,1,1,0,1,1],
      [1,1,1,1,1,1]]

#미로 출력
def print_maze(maze):
    print("=====MAZE=====")
    for r in maze:
        for p in r:
            print(p, end=" ")
        print()
    print("==============")

#탐색 알고리즘
def DFS(maze):    
    s = Stack()
    x,y = 0,1
    s.push( (x,y) ) #시작점
    
    while maze[y][x] != 'X':
        if not s.emt():
            maze[y][x] = 'M'  #지나온 위치
            (x,y) = s.pop()
            if maze[y][x] == "X":
                print_maze(maze)
                print("수고하셨습니다.")
                break
            maze[y][x] = 'I'  #현재 위치
            print_maze(maze)
            
            #갈 수 있는 길 탐색
            if maze[y][x+1] in (0,'X'):          #우측
                s.push( (x+1,y) )
            if maze[y][x-1] in (0,'X'):          #좌척
                s.push( (x-1,y) )
            if maze[y-1][x] in (0,'X'):          #위
                s.push( (x,y-1))
            if maze[y+1][x] in (0,'X'):          #아래
                s.push( (x,y+1) )
            print(s.stack,'\n')
            
        else:
            print("더 이상 갈 수 있는 길이 없습니다.")
            break
DFS(maze)