자료구조 | Maze Problem | linear DS

미로 탈출하기

• 문제 : 입구로부터 출구로 나가는 길을 찾아라!
• 조건 : 0은 움직일 수 있는 길, 1은 불가능한 길이다. 
• 방향 : 상하좌우, 대각선으로 움직일 수 있다. 

 

추가적인 안내

미로는 2차원 배열에 구현되어 있다. 

입구는 maze[0][0]이고, 출구는 maze[row-1][col-1]이다.

나가는 길을 찾기 위해 move[0] move[1] move[2] move[3] 을 사용할 수 있다. maze[next_row][next_col] = ?

 

mark라는 배열을 만들어 지나온 길을 기록해둔다. mark = [[0]*10 for i in range(10)]

mark=[[0]*10 for i in range(10)]
print(mark)

 

path stack

backtracking을 위한 stack으로, 새로운 장소로 이동할때마다 row, col을 저장한다.

만약에 더 이상 갈 곳이 없으면, 이전 장소에서 다른 방향으로 이동한다. 

path stack이 empty가 되면, fail하는 것이고

path stack을 다 채우면 solution이 된다. 

 

예상 출력

Path found :
stack [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), 
(6, 2), (6, 3), (7, 3), (7, 4), (7, 5), (6, 5), (6, 6), (6, 7), (7, 7), 
(7, 8), (8, 8)]

 

구현

스켈레톤 코드

class Maze:
    def __init__(self):
        self.maze = [[1,1,1,1,1,1,1,1,1,1],\
                     [1,0,0,1,0,0,0,0,1,1], \
                     [1,1,0,1,0,1,1,0,0,1],\
                     [1,0,0,0,0,1,1,1,1,1],\
                     [1,0,1,1,0,1,0,0,0,1],\
                     [1,0,0,1,0,1,1,0,1,1],\
                     [1,1,0,0,1,0,0,0,1,1],\
                     [1,1,1,0,0,0,1,0,0,1], \
                     [1,0,0,0,1,0,1,1,1,1],\
                     [1,1,1,1,1,1,1,1,1,1]]
        self.mark = []
        self.stack = []
        self.found = False
    def empty(self):
        pass
    def push(self, row, col):
        pass
    def view(self):
        pass
    def explore(self):
        pass

히힛 풀었다 :D

class Maze:
    def __init__(self):
        self.maze = [[1,1,1,1,1,1,1,1,1,1],\
                     [1,0,0,1,0,0,0,0,1,1], \
                     [1,1,0,1,0,1,1,0,0,1],\
                     [1,0,0,0,0,1,1,1,1,1],\
                     [1,0,1,1,0,1,0,0,0,1],\
                     [1,0,0,1,0,1,1,0,1,1],\
                     [1,1,0,0,1,0,0,0,1,1],\
                     [1,1,1,0,0,0,1,0,0,1], \
                     [1,0,0,0,1,0,1,1,0,1],\
                     [1,1,1,1,1,1,1,1,1,1]]
        self.mark = [[0]*10 for i in range(10)]
        self.stack = [[1,1]]
        self.found = False
    def empty(self):
        return len(self.stack) == 0
    def push(self, row, col):
        self.stack.insert(0, [row, col])
    def view(self):
        for i in self.maze:
            print(i)
    def explore(self):
        while True:
            self.mark[1][1] = 1
            if len(self.stack) == 0:
                print("FAILED")
                return 
            elif self.stack[0] == [8,8]:
                print("Solution : ", self.stack)
                return
            else:
                self.found = False
                tmp = self.stack[0]
                if self.maze[tmp[0]-1][tmp[1]]==0 and \
                    self.mark[tmp[0]-1][tmp[1]]==0 :
                    self.found = True
                    self.nextCandid = [tmp[0]-1, tmp[1]]
                elif self.maze[tmp[0]+1][tmp[1]]==0 and \
                    self.mark[tmp[0]+1][tmp[1]]==0 :
                    self.found = True     
                    self.nextCandid = [tmp[0]+1, tmp[1]]           
                elif self.maze[tmp[0]][tmp[1]-1]==0 and \
                    self.mark[tmp[0]][tmp[1]-1]==0 :
                    self.found = True          
                    self.nextCandid = [tmp[0], tmp[1]-1]       
                elif self.maze[tmp[0]][tmp[1]+1]==0 and \
                    self.mark[tmp[0]][tmp[1]+1]==0 :
                    self.found = True 
                    self.nextCandid = [tmp[0], tmp[1]+1]
                    
                if self.found == True:
                    self.stack.insert(0, self.nextCandid)
                    self.mark[self.nextCandid[0]][self.nextCandid[1]] = 1
                    print(self.stack)
                else:
                    tmp = self.stack.pop(0)
                    



m = Maze()
m.explore()