스택 미로 탐색 문제

미로 탐색 문제

미로를 탈출하기 위한 기본적인 방법은 시행 착오 방법 이 있다.

하나의 경로를 선택하여 시도해보고 막힌 길이라면 다른 경로를 시도해야 한다. 이때 현재 위치에서 가장 가까운 경로를 찾는 것이 효율적이므로 가장 최근에 저장한 경로가 쉽게 추출되는 스택이 해당 문제풀이에 어울리는 자료구조이다.

소스코드

from stack import Stack

class Element:
    def __init__(self, row, col):
        self.row = row
        self.col = col

'''
길 : 0 
벽 : 1 
이미 지나온 위치 : . 
목표 지점 : x
'''
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 'x'],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

def push_loc(s, r, c):
    # 미로를 벗어나는 범위일 경우 아무것도 하지않고 return 한다.
    if r < 0 or c < 0:
        return

    # 벽과 지나온 위치가 아닐 경우 스택에 이동 가능한 경로를 push 한다.    
    if maze[r][c] != 1 and maze[r][c] != '.':
        tmp = Element(r, c)
        s.push(tmp)    

if __name__ == "__main__":
    # 이동 위치를 담을 스택 선언.
    s = Stack()

    # 시작 위치를 초기화한다.
    here = Element(1, 0)

    # 목표에 도착할 때 까지 반복.
    while maze[here.row][here.col] != 'x':

        # 상, 하, 좌, 우 로 움직일 위치가 있는지 확인 후 스택에 저장한다.
        push_loc(s, here.row - 1, here.col)
        push_loc(s, here.row + 1, here.col)
        push_loc(s, here.row, here.col - 1)
        push_loc(s, here.row, here.col + 1)

        # 만약 스택이 비었다면 반복문을 마친다.
        if s.is_empty():
            print("실패")
            exit()

        # 스택에서 pop 하여 현재 위치로 변경한다.
        else:
            maze[here.row][here.col] = '.'
            tmp = s.pop()
            here.row = tmp.row
            here.col = tmp.col

    print("성공")

출력

성공