미로찾기 - BFS(Queue)

Queue

Queue는Tail에서는 Insert, Head에서는 Delete가 이루어지는 구조이다. 흔히 매표소를 비유한다.

First in, First out이다.

위키백과

성능

Insert: O(1)

Delete: O(1)

 

간단한 구현

 

Queue를 이용한 미로찾기

1. 현재 위치에서 갈 수 있는 모든 위치를 Queue에 넣는다.

2. Queue에서 위치를 꺼내서 전진한다.

3. Queue가 비었으면 실패한다.

4. 오른쪽 맨 아래에 도착하면 성공한다.

 

BFS 미로찾기의 정확성

DFS 미로찾기와 비슷하다. 갈수 있는 모든 곳은 Queue에 넣으므로 도착지점까지의 좌표 sequence가 있으면 항상 방문한다.