[Python 자료구조 #큐3] 우선순위 큐, 미로 찾기

* 우선순위 큐(priority queue)

• 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어지지만, 특별한 언급이 없으면 우선순위 큐는 가장 높은 우선순위의 요소가 먼저 삭제되는 최대 우선순위 큐를 의미한다.
• 실제로 가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는 힙(heap)이다. (여기서는 리스트를 이용해서 구현할 것임.)
• 단순화를 위해 데이터 자체가 우선순위를 나타낸다고 가정한다. 일반적으로는 (데이터, 우선순위) 형식의 튜플 구조가 바람직하다.

from Stack import*	# 이전 포스팅에서 만든 stack.py 모듈을 가져왔다.

class PriorityQueue :	# 우선순위 큐 클래스 생성
    def __init__( self ):					
        self.items = []						

    def isEmpty( self ):					
        return len( self.items ) == 0
    def size( self ): return len(self.items)
    def clear( self ): self.items = []		

    def enqueue( self, item ):		# 삽입 연산
        self.items.append( item )	# 리스트의 맨 뒤에 삽입(시간복잡도 O(1))

    def findMaxIndex( self ):		# 최대 우선순위 항목의 인덱스 반환
        if self.isEmpty(): return None
        else:
            highest = 0						
            for i in range(1, self.size()) :
                if self.items[i] > self.items[highest] :
                    highest = i	
            return highest		


    def dequeue( self ):		# 삭제 연산
        highest = self.findMaxIndex()		
        if highest is not None :
            return self.items.pop(highest)	

    def peek( self ):				#peek 연산
        highest = self.findMaxIndex()	
        if highest is not None :
            return self.items[highest]

우선순위 큐 적용 예시:

q = PriorityQueue()
q.enqueue( 34 )
q.enqueue( 18 )
q.enqueue( 27 )
q.enqueue( 45 )
q.enqueue( 15 )

print("PQueue:", q.items)
while not q.isEmpty() :
    print("Max Priority = ", q.dequeue() )
-------------------------------------------------------
PQueue: [34, 18, 27, 45, 15]
Max Priority =  45
Max Priority =  34
Max Priority =  27
Max Priority =  18
Max Priority =  15

 

* 우선순위 큐의 응용 : 전략적인 미로 탐색

• 우선순위 큐에 미로에서의 현위치를 저장한다. 큐는 [x,y,distance] 위치 정보를 가지는 리스트들의 모음이다. 고로 최고 우선순위 항목을 찾기 위해서는 distance의 값을 비교해야하고, 인덱스[_][2]로 표시된다.
• 위에 PriorityQueue 클래스에 있는 findMaxIndex 함수를 아래와 같이 변경해준다.

    def findMaxIndex(self):
        if self.isEmpty():
            return None
        else:
            highest = 0
            for i in range(1, self.size()):
                if self.items[i][2] > self.items[highest][2]:	# [i][2]는 distance값을 나타낸다. [x, y, distance]
                    highest = i
            return highest

from PriorityQueue import * # 앞서 만들어 놓은 우선순위 큐 모듈을 불러온다.

import math # 내장라이브러리 math 모듈을 불러온다.


def dist(x, y):
    (dx, dy) = (ox - x, oy - y)
    return math.sqrt(dx * dx + dy * dy)


def isValidPos(x, y):
    if x < 0 or y < 0 or x >= MAZE_SIZE or y >= MAZE_SIZE:
        return False
    else:
        return map[y][x] == "0" or map[y][x] == "x"	# 위치(x, y)는 리스트의 요소인 튜플을 지정한다.


def MySmartSearch():
    q = PriorityQueue()
    q.enqueue((0, 1, -dist(0, 1)))	# 출발 위치에 대한 튜플을 우선순위 큐에 저장한다.
    print("PQueue: ")

    while not q.isEmpty():
        here = q.dequeue()
        print(here[0:2], end="->")	# 현위치 [X, Y, distance] 표시
        x, y, _ = here	# 언더바도 변수 이름이다. 변수 저장 형식을 맞추기 위해 distance를 변수(언더바)에 저장한 것일뿐이다.
        if map[y][x] == "x":	# 여기서 x는 출구를 뜻하는 문자열이다.
            return True
        else:
            map[y][x] = "."	# 지나온 자리 표시
            if isValidPos(x, y - 1):	# 상 방향 검사
                q.enqueue((x, y - 1, -dist(x, y - 1)))
            if isValidPos(x, y + 1):	# 하 방향 검사
                q.enqueue((x, y + 1, -dist(x, y + 1)))
            if isValidPos(x - 1, y):	# 좌 방향 검사
                q.enqueue((x - 1, y, -dist(x - 1, y)))
            if isValidPos(x + 1, y):	# 우 방향 검사
                q.enqueue((x + 1, y, -dist(x + 1, y)))
        print("우선순위큐: ", q.items)
    return False

미로탐색 예시:

(ox, oy) = (5, 4)  # 출구 위치
map = [
    ["1", "1", "1", "1", "1", "1"],  # 미로
    ["e", "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"],
]
MAZE_SIZE = 6  # 정사각형 미로 크기
result = MySmartSearch()
if result:
    print(" --> 미로탐색 성공")
else:
    print(" --> 미로탐색 실패")
----------------------------------------------------------------------------------------------
PQueue: 
(0, 1)->우선순위큐:  [(1, 1, -5.0)]
(1, 1)->우선순위큐:  [(1, 2, -4.47213595499958)]
(1, 2)->우선순위큐:  [(1, 3, -4.123105625617661), (2, 2, -3.605551275463989)]
(2, 2)->우선순위큐:  [(1, 3, -4.123105625617661), (3, 2, -2.8284271247461903)]
(3, 2)->우선순위큐:  [(1, 3, -4.123105625617661), (3, 1, -3.605551275463989), (3, 3, -2.23606797749979)]
(3, 3)->우선순위큐:  [(1, 3, -4.123105625617661), (3, 1, -3.605551275463989), (3, 4, -2.0)]
(3, 4)->우선순위큐:  [(1, 3, -4.123105625617661), (3, 1, -3.605551275463989), (4, 4, -1.0)]
(4, 4)->우선순위큐:  [(1, 3, -4.123105625617661), (3, 1, -3.605551275463989), (5, 4, -0.0)]
(5, 4)-> --> 미로탐색 성공

아래 그림은 탐색 순서와 현재 위치에 대한 튜플(x,y) 그리고 리스트의 인덱스를 비교하는 표이다.

map[y][x]	[y][0]	[y][1]	[y][2]	[y][3]	[y][4]	[y][5]
map[0]
map[1]	1(e)	2
map[2]		3 (1,2)	4	5 (3,2)
map[3]				6
map[4]				7	8	9(x)
map[5]

※ 파이썬에서 언더 바의 사용

https://blog.naver.com/jkg57/222222700891