[Python 자료구조 #스택3] 미로 탐색

* 깊이 우선 탐색(Depth-First-Search, DFS)

출처 : https://developer-mac.tistory.com/64

 

* 너비 우선 탐색(Breadth-Firs-Search, BFS)

출처 : https://developer-mac.tistory.com/64

* 미로탐색 알고리즘

from Stack import *


def isValidPos(x, y):
    if x < 0 or y < 0 or x >= MAZE_SIZE or y >= MAZE_SIZE:
        return False
    else:
        return map[y][x] == "0" or map[y][x] == "x"	# (x,y)는 리스트에서 [y][x]가 된다.


def DFS():
    stack = Stack()
    stack.push((0, 1))
    print("DFS: ")

    while not stack.isEmpty():
        here = stack.pop()
        print(here, end="->")
        (x, y) = here
        if map[y][x] == "x":
            return True
        else:
            map[y][x] = "."

            if isValidPos(x, y - 1):  # 탐색순서가 상하좌우 깊이 우선 탐색방법
                stack.push((x, y - 1))  # 스택에 마지막으로 추가된 값이 현재 위치가 된다.
            if isValidPos(x, y + 1):  
                stack.push((x, y + 1))
            if isValidPos(x - 1, y):
                stack.push((x - 1, y))
            if isValidPos(x + 1, y):
                stack.push((x + 1, y))
        print(" 현재 스택: ", stack)
    return False


map = [
    ["1", "1", "1", "1", "1", "1"],
    ["e", "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"],
]
MAZE_SIZE = 6
result = DFS()
if result:
    print(" --> 미로탐색 성공")
else:
    print(" --> 미로탐색 실패")

 

실행결과

DFS:
(0, 1)-> 현재 스택:  [(1, 1)]
(1, 1)-> 현재 스택:  [(1, 2), (2, 1)]        
(2, 1)-> 현재 스택:  [(1, 2), (3, 1)]        
(3, 1)-> 현재 스택:  [(1, 2), (3, 2), (4, 1)]
(4, 1)-> 현재 스택:  [(1, 2), (3, 2)]        
(3, 2)-> 현재 스택:  [(1, 2), (3, 3)]
(3, 3)-> 현재 스택:  [(1, 2), (3, 4), (4, 3)]
(4, 3)-> 현재 스택:  [(1, 2), (3, 4), (5, 3)]
(5, 3)-> --> 미로탐색 성공