[자료구조] 큐 - BFS 미로 탐색

728x90

 

 

 

🙆‍♂️ 원형 큐 class

---

"""
원형 큐 클래스 CQueue
def emt : 큐에 값이 없다면 True를 반환 있다면 False를 반환
def full : 큐가 포화상태라면 True를 반환 아니라면 False를 반환
def clear : 큐 초기화
def enqueue : 포화상태가 아니면서 알파벳 값(ch)만 추가
def dequeue : 공백상태가 아니라면 최전단값 반환하고 제거
def peek : 큐의 최전단값 반환
def size : 큐의 길이 반환
def display : 현재 큐 상태 출력
"""
MAX_SIZE = 100
class CQueue:
    def __init__(self):
        self.front=0
        self.rear=0
        self.items=[None] * MAX_SIZE
    def emt(self):
        return self.front==self.rear
    def full(self):
        return self.front == (self.rear+1)%MAX_SIZE
    def clear(self):
        self.front = self.rear
        
    """
    enqueue(self,ch) : 입력
    1. 포화상태 검사
    2. rear 한칸 뒤로 이동
    3. rear 맨뒤에 값 입력
    """
    def enqueue(self,ch):
        if not self.full():
            self.rear = (self.rear+1)%MAX_SIZE
            self.items[self.rear] = ch
            
    """
    dequeue(self) : 출력
    1. 공백상태인지 검사
    2. front 한 칸 앞으로 이동
    3. 삭제된 값 반환
    """
    def dequeue(self):
        if not self.emt():
            self.front = (self.front+1)%MAX_SIZE
            return self.items[self.front]
    def peek(self):
        if not self.emt():
            return self.items[(self.front+1)%MAX_SIZE]
    def size(self):
        return abs(self.rear - self.front)
    def display(self):
        output = []
        if self.front < self.rear:
            output = self.items[self.front+1 : self.rear+1]
        else:
            output = self.items[self.front+1 : MAX_SIZE] + self.items[0:self.rear+1]            
        print(output)

 

🙋‍♂️ BFS 미로 탐색

---

"""
큐를 이용한 BFS 미로 탐색
"""

#미로 정의
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]]

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


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

while not road.emt():
    here = road.dequeue()
    print_maze(maze)
    print(here,end=" >> \n")
    x,y=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))
    if maze[y+1][x] in (0,'X'):          #하
        road.enqueue((x,y+1))
    if maze[y][x+1] in (0,'X'):          #우
        road.enqueue((x+1,y))
    if maze[y][x-1] in (0,'X'):          #좌
        road.enqueue((x-1,y))