[자료구조] 스택(Stack)을 이용한 미로찾기 (5)

미로찾기

- 이미 방문한 위치는 표시를 해서 무한루프를 방지한다.

- 현재 위치에서 일정한 규칙으로 다음 위치로 이동한다.

   ㄴ 북, 동 남, 서의 순으로 검사하여 그 방향으로 갈 수 있다면

       Tip. 즉 방문하지 않은 위치면서 벽이 아니면 그 방향으로 간다.

- 아무 방향으로도 갈 수 없으면 그 위치에 오기 직전 위치로 회귀한다.

 

 

# 프로그램의 구조로 표현

1. 현재 위치는 출발점(0, 0)이다.

2. 다음을 반복한다.

     1) 현재 위치에 방문했다는 표시를 한다.

     2) 현재 위치가 출구라면 종료한다.

     3) 현재 위치에서 북, 동, 남, 서 4방향에 대해서 순서대로 이동할 수 있는지(벽 x, 외부 x, 방문한 위치 x) 검사

     4) 갈 수 있다면 현재 위치를 스택에 push 후 그 방향으로 이동

     5) 3번에서 어느 방향으로 가지 못했다면 스택에서 pop한 후 그 위치로 돌아간다 (돌아갈 위치가 없다면 길이 없는 미로)

 

 

# python 코드

PATH = 0 # 지나갈 수  있는 위치
WALL = 1 # 지나갈 수  없는 위치
VISITED = 2 # 이미 방문한 위치
BACKTRACKED = 3 # 방문 했다가 되돌아 나온 위치

X = 0
Y = 1

maze = [[0,0,0,0,1,0,0,0],
        [0,1,1,0,1,0,1,1],
        [0,0,1,1,1,1,1,1],
        [0,0,0,0,0,0,0,1],
        [1,0,1,1,1,1,0,1],
        [0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,1,1],
        [0,0,0,0,0,0,0,0]] # 미로 배열
n = len(maze) # 미로의 크기


offset = [(-1,0),(0,1),(1,0),(0,-1)]
def movable(pos ,di):
    x = pos[X] + offset[di][0]
    y = pos[Y] + offset[di][1]
    
    if (x<0 or x>=n or y<0 or y>=n):
        return False
    elif (maze[x][y]== WALL or maze[x][y]==BACKTRACKED or maze[x][y]==VISITED):
        return False
    else:
        return True

def move_to(pos,di):
    x = pos[X] + offset[di][0]
    y = pos[Y] + offset[di][1]
    
    return (x,y)

def run_maze(maze):
    s = [] # 스택 선언
    cur = (0,0) # 현재 위치를 튜플로 선언

    while(1):
        maze[cur[X]][cur[Y]] = VISITED # 현재 위치를 방문했다고 표시
        if (cur[X] == n-1 and cur[Y] == n-1): # 현재 위치가 출구라면 끝
            print("Found the path")
            break
        
        forwarded = False # 4 방향 중 한 곳으로 전진하는데 성공했는지 표시
        for i in range(4): # 0:N , 1:E, 2:S, 3:W
            if (movable(cur,i)): # 해당 방향으로 이동할 수 있는지 검사
                s.append(cur)    # 현재 위치를 stack에 푸쉬
                cur = move_to(cur, i) # 해당 방향으로 한칸 이동한 위치를 새로운 cur로 지정한다
                forwarded = True
                break
        if not forwarded:
            maze[cur[X]][cur[Y]] = BACKTRACKED # 방문했다가 되돌아간 위치임을 표시
            if len(s) == 0:
                print("No path exists")
                break
            cur = s.pop()

run_maze(maze)