파이썬 알고리즘 - 2.2 미로 문제

2.2 미로 문제

 미로에서 길을 찾는건 컴퓨터 과학에서 가장 흔히 다루는 탐색 문제라고 할수 있습니다. 여기서 사용할 지도는 2차원 그리드 셀로 되어있으며, 여기서 셀 cell이란 문자열로 빈 공간은 " ", 막힌 공간은 "X"로 표시하겠습니다. 이 외에도 시작점, 도착지, 경로등을 나타내기위해 아래와 같이 정의하겠습니다.

 

 

2.2.1 임의의 미로 생성하기

 이제 만들 Maze 클래스는 2차원 그리드로(리스트의 리스트)로 상태를 나타내려고 하는데, 이 상태들의 종류로는 행의 수, 열의 수, 시작 위치, 목적지, 긜고 임의로 막힌 공간들이 있겠습니다.

 

 미로는 시작지점과 도착지를 지정하면, 이에 대한 경로가 존재하도록 희박해져야 하는데, 일단 새 미로를 호출할때 희소 정도를 명시하도록하고, 기본값으로 20%정도 블록으로 설정하겠습니다. 

 

#file_name : maze.py
from enum import Enum
from typing import NamedTuple
import random

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 = 10, columns = 10, sparseness = 0.2, start = MazeLocation(0, 0), goal = MazeLocation(9, 9)):
        self._rows = rows
        self._columns = columns
        self.start = start
        self.goal = goal
        self._grid = [[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, columns, sparseness):
        for row in range(rows):
            for column in range(columns):
                # 균일 분포로 생성한 확률이 희소 임계치보다 작은 경우에만 블록
                if random.uniform(0, 1.0) < sparseness:
                    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

maze = Maze()
print(maze)

 

 

2.2 다른 세부사항들

 목적지를 탐색하는 함수를 구현하기 전에 우선 MazeLocation이 도착지에 도달했는지 확인할수 있어야 하는데 이 함수를 Maze 클래스에 추가해 줍시다.

    def goal_test(self, ml):
        return ml == self.goal

 

 그 다음으로 미로 상에 어느 위치가 주어지면 이 곳에서 수직이나 수평으로 움직일수 있는지 확인하여야 합니다. ㅎ함수 successors()로 해당 위치에서 가능한 다음 위치를 찾아볼수 있도록 구현하겠습니다. 이 함수는 단순하게 위, 아래, 오른쪽, 왼쪽이 빈 공간인지만 확인하는 것으로 지도의 가장자리는 확인을 해서는 안됩니다. 반환 값은 이동 가능한 모든 MazeLocation이 되겠습니다.

 

    def succesors(self, ml):
        locations = []
        # 오른쪽이 미로 범위 안이고, 막히지 않은 경우
        if ml.row + 1 < self._rows and self._grid[ml.row+1][ml.colum] != 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._column 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.colum - 1] != Cell.BLOCKED:
            location.append(MazeLocation(ml.row, ml.column - 1))
        return locations