Programming 기초/Python
[Python 자료구조 #큐3] 우선순위 큐, 미로 찾기
코딩상륙작전
2023. 5. 15. 14:33
* 우선순위 큐(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 highestfrom 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] |
※ 파이썬에서 언더 바의 사용