[자료구조] 큐 - 우선순위 큐를 활용한 미로 탐색

728x90

 

 

 

🙆‍♂️ 우선순위 큐

---

"""
우선순위 큐
"""

class PQueue:
    def __init__(self):
        self.items = []
    def emt(self):
        return len(self.items)==0
    def size(self):
        return len(self.items)
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if not self.emt():
            maxI = 0
            high =  self.items[maxI][2]
            for i in range(1,self.size()):
                if self.items[i][2] > high:
                    high = self.items[i][2]
                    maxI = i
            return self.items.pop(maxI)

미로 탐색을 위해 살짝 변경된 우선순위 큐입니다.

 

🙋‍♂️ 우선순위 미로 탐색

---

"""
우선순위 큐를 이용한 미로 탐색
"""

#미로 정의
maze = [[1,1,1,1,1,1],
        ['H',0,1,0,0,1],
        [1,0,0,0,1,1],
        [1,0,1,0,1,1],
        [1,0,1,0,0,'X'],
        [1,1,1,1,1,1]]

goalPos = (5,4)   #출구

def dis(x,y):
    return -((goalPos[0]-x)**2 + (goalPos[1]-y)**2)**(1/2)

#미로 출력
def print_maze(maze):
    print("=====MAZE=====")
    for r in maze:
        for p in r:
            print(p, end=" ")
        print()
    print("==============")


road = PQueue()
road.enqueue( (0,1,dis(0,1)) )
print("Start : ")

while not road.emt():
    here = road.dequeue()
    print_maze(maze)
    print(here,end=" >> \n")
    x,y,d=here
    if maze[y][x] == 'X':
        break
    else:
        maze[y][x] = "v"
        
    #탐색 알고리즘
    if maze[y-1][x] in (0,'X'):             #상
        road.enqueue((x,y-1,dis(x,y-1)))
    if maze[y+1][x] in (0,'X'):             #하
        road.enqueue((x,y+1,dis(x,y+1)))
    if maze[y][x+1] in (0,'X'):             #우
        road.enqueue((x+1,y,dis(x+1,y)))
    if maze[y][x-1] in (0,'X'):             #좌
        road.enqueue((x-1,y,dis(x-1,y)))

다른 미로 탐색과는 다르게 빠릅니다.