[python/파이썬] 미로찾기: DFS 깊이 우선 탐색 알고리즘 방법 적용

maze.py

from enum import Enum
from typing import List, NamedTuple, Callable, Optional
import random
from math import sqrt
from urllib.parse import MAX_CACHE_SIZE
from generic_search import dfs, node_to_path, Node #, bfs, astar

class Cell(str, Enum):
    EMPTY = " "
    BLOCKED = "X"
    START = "S"
    GOAL = "G"
    PATH = "*"

class MazeLocation(NamedTuple):
    row: int
    column: int

class Maze:
    def __init__(self, rows: int = 10
                ,columns: int = 10
                ,sparseness: float = 0.2
                ,start: MazeLocation = MazeLocation(0,0)
                ,goal: MazeLocation = MazeLocation(9,9)):
        
        # 기본 인스턴스 변수 초기화
        self._rows: int = rows
        self._columns: int = columns
        self.start: MazeLocation = start
        self.goal: MazeLocation = goal
        
        # 격자를 빈 공간으로 채운다.
        self._grid: List[List[Cell]] = [[Cell.EMPTY for c in range(columns)] for r in range(rows)]
        
        # 격자에 막힌 공간을 무작위로 채운다.
        self._randomly_fill(rows, columns, sparseness)
        
        # 시작 위치와 목표 위치를 설정한다.
        self._grid[start.row][start.column] = Cell.START
        self._grid[goal.row][goal.column] = Cell.GOAL
        
    def _randomly_fill(self, rows: int, columns: int, sparseness: float):
        for row in range(rows):
            for column in range(columns):
                if random.uniform(0, 1.0) < sparseness: # 무작위수가 0.2보다 작으면 X로 막는다.
                    self._grid[row][column] = Cell.BLOCKED

    # 미로 출력
    def __str__(self):
        output = ""
        for row in self._grid:
            output += "".join([c.value for c in row]) + "\n"
        return output

    def goal_test(self, ml: MazeLocation):
        return ml == self.goal
    
    # 말의 움직임 설정
    def successors(self, ml: MazeLocation):
        locations: List[MazeLocation] = []
        # 상위 행으로 이동시
        if ml.row + 1 < self._rows and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row + 1, ml.column))
        # 하위 행으로 이동시
        if ml.row - 1 >= 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row - 1, ml.column))
        # 열 한칸 앞으로 이동시
        if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column + 1))
        # 열 한칸 뒤로 이동시
        if ml.column - 1 >= 0 and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column - 1))
            
        return locations
    
    def mark(self, path: List[MazeLocation]):
        for maze_location in path:
            self._grid[maze_location.row][maze_location.column] = Cell.PATH
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL
        
    def clear(self, path: List[MazeLocation]):
        for maze_location in path:
            self._grid[maze_location.row][maze_location.column] = Cell.EMPTY
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL

if __name__ == "__main__":
    # 깊이 우선 탐색(DFS)
    m: Maze = Maze()
    print(m)
    
    solution1: Optional[Node[MazeLocation]] = dfs(m.start
                                                 ,m.goal_test
                                                 ,m.successors)
    if solution1 is None:
        print("깊이 우선 탐색으로 길을 찾을 수 없습니다!")
    else:
        path1: List[MazeLocation] = node_to_path(solution1)
        m.mark(path1)
        print(m)
        m.clear(path1)

 

generic_search.py

# maze.py 파일에 필요한 라이브러리를 이미 import 했으므로 추가할 필요는 없음.
from __future__ import annotations # 파이썬 3.8이상에선 없어도 무방하지만, 파이썬3.7 이하에선 있어야함
from typing import TypeVar, Iterable, Sequence, Generic, List, Callable, Set, Deque, Dict, Any, Optional
from typing_extensions import Protocol
from heapq import heappush, heappop

T = TypeVar('T')

def linear_contains(iterable: Iterable[T], key: T):
    for item in iterable:
        if item == key:
            return True
    return False

C = TypeVar("C", bound="Comparable")

class Comparable(Protocol):
    def __eq__(self, other: Any):
        ...
    def __lt__(self: C, otehr: C):
        ...
    def __gt__(self: C, other: C):
        return (not self < other) and self != other
    def __le__(self: C, other: C):
        return self < other or self == other
    def __ge__(self: C, other: C):
        return not self < other
    
    def binary_contains(sequence: Sequence[C], key: C):
        low: int = 0
        high: int = len(sequence) - 1
        while low <= high: # 검색 공간(범위)이 있을 때까지 수행
            mid: int = (low + high) // 2
            if sequence[mid] < key:
                low = mid + 1
            elif sequence[mid] > key:
                high = mid - 1
            else:
                return True
        return False

class Stack(Generic[T]):
    def __init__(self):
        self._container: List[T] = []
        
    @property
    def empty(self):
        return not self._container # 컨테이너가 비었다면 false가 아니다(= true)
    
    def push(self, item: T):
        self._container.append(item)
    
    def pop(self):
        return self._container.pop() # 후입선출(LIFO)
    
    def __repr__(self):
        return repr(self._container)

class Node(Generic[T]):
    def __init__(self
                ,state: T
                ,parent: Optional[Node]
                ,cost: float = 0.0
                ,heuristic: float = 0.0):
        
        self.state: T = state
        self.parent: Optional[Node] = parent
        self.cost: float = cost
        self.heuristic: float = heuristic
    
    def __lt__(self, other: Node):
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)
    
def dfs(initial: T
       ,goal_test: Callable[[T], bool]
       ,successors: Callable[[T], List[T]]):
    
    # frontier는 아직 방문하지 않은 곳이다.
    frontier: Stack[Node[T]] = Stack()
    frontier.push(Node(initial, None))
    # explored는 이미 방문한 곳이다.
    explored: Set[T] = {initial}
    
    # 방문한 곳이 더 있는지 탐색한다.
    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state: T = current_node.state
        # 목표 지점을 찾았다면 종료한다.
        if goal_test(current_state):
            return current_node
        # 방문하지 않은 다음 장소가 있는지 확인한다.
        for child in successors(current_state):
            if child in explored: # 이미 방문한 자식 노드(장소)라면 건너뛴다.
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))
            
    return None # 모든 곳을 방문했지만 결국 목표 지점을 찾지 못했다.

def node_to_path(node: Node[T]):
    path: List[T] = [node.state]
    # 노드 경로를 반전한다.
    while node.parent is not None:
        node = node.parent
        path.append(node.state)
    path.reverse()
    return path

 

미로

S       X 
  XX     X
  X   XX  
   X   XX 
       X X
      X   
X        X
X    X    
    XX   X
 X X X   G

경로 찾기 결과

S*****  X 
  XX *   X
  X **XX  
   X*  XX 
 ****  X X
 *    X   
X********X
X    X  * 
    XX  *X
 X X X  *G