![[Algorithm] 큐(Queue)와 BFS](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
- Queue
- Queue의 구현: 선형 큐
- 원형 큐
- 원형 큐의 구현
- 우선순위 큐(Priority Queue)
- 큐의 활용 : 버퍼(Buffer)
- BFS
- 번외 : Deque
- 번외 : DFS VS BFS
Queue
Queue의 특성
- 삽입과 삭제의 위치가 제한적인 자료구조(스택처럼)
- 큐는 삽입은 뒤에서만, 삭제는 앞에서만
- 선입선출구조(FIFO; First In First Out)
Queue의 선입선출 구조
- 머리(Front) : 저장된 원소 중 첫 번재 원소 또는 삭제된 위치
- 꼬리(Rear) : 저장된 원소 중 마지막 원소(가장 신입 원소)
Queue의 연산
-
enQueue(item) : 삽입. rear 다음에 원소 삽입
-
deQueue() : 삭제. front 원소 삭제 후 반환
-
Qpeek() : 반환. front 원소 삭제 없이 반환
-
createQueue() : 공백 queue 생성
-
isEmpty() : queue가 공백인지 확인
-
isFull() : queue가 포화인지 확인
Queue의 구현: 선형 큐
선형 큐
- 1차원 배열 이용
- 큐의 크기 = 배열의 크기
- front
- 첫 번째 원소의 index 직전의 인덱스
- 추가하게 deQueue를 하려면 front를 한 칸 뒤로 옮기고 dequeue
- rear : 마지막 원소의 index
왜 front는 맨 앞 원소 이전의 빈 공간의 인덱스인가요?
A. 상태를 보다 쉽게 알기 위해서!!
- dequeue에 의해 front가 이동하다가 rear까지 오면 곧 front와 rear가 같은 빈 공간을 가리킨다는 것
- queue가 비어있다면 front와 rear가 같은 상황이기 때문에 이거만 체크해주면 된다!
상태 표현
- 초기 : front = rear = -1
- 공백 : front == rear
- 포화 : rear == n-1(배열의 마지막 인덱스)
초기 공백 큐 생성
- 크기 n인 1차원 배열 생성
- front와 rear을 -1로 초기화
Q = [0]*n
front = rear = -1
삽입: enQueue(item)
- rear + 1 : 새로운 원소 삽입 자리 마련
- rear 인덱스에 해당하는 배열원소 Q[rear]에 item 저장
def enQueue(item):
global rear
if isFull():
print("Queue_Full")
else:
rear += 1
Q[rear] = item
삭제: deQueue()
- 가장 앞의 원소 삭제(한다고 가정)
- front + 1 : 큐에 남을 첫 번째 원소 표시 이동
- 새로운 첫 번째 원소 return
def deQueue():
if isEmpty():
print("Queue_Empty")
else:
front += 1
return Q[front]
실제로는 큐에 데이터가 남지만 front가 이동하며 돌아갈 일이 없으니까 삭제하는 것으로 가정
검색: Qpeek()
- 가장 앞의 원소 검색 후 반환
- front 한 자리 뒤(front+1)의 원소, 즉 큐의 첫 번째 원소 반환
def Qpeek():
if isEmpty():
print("Queue_Empty")
else:
return Q[front+1]
공백/포화 검사
- 공백 : front == rear
- 포화 : rear == n-1
def isEmpty():
return front == rear
def isFull():
return rear == len(Q) - 1
선형 큐 이용 시 주의사항
포화상태의 오인?
원소의 삽입/삭제의 반복 시 배열의 앞 부분에 활용할 수 있는 공간이 있음에도 rear가 n-1이 되면 포화상태로 인식하게 된다.
해결방안 1
- 매 연산 후 저장된 원소들을 배열의 앞부분으로 모두 이동
- 큐의 효율성 급격히 감소 : 원소 이동에 시간 소요
해결방안 2
- 논리적으로는 배열의 처음과 끝이 연결되어 원형이라고 가정
- 실제로는 1차원 배열
원형 큐
- 초기 : front = rear = 0
- index 순환
- front와 rear의 위치가 n-1을 가리킨다.
- 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동
mod(%)를 이용
원형 큐의 구조
- 공백/포화를 쉽게 구분하기 위해 front 자리 사용 X : front는 빈 자리
- front를 제외한 나머지가 가득 찼다면 Full
삽입 위치
- 선형 큐 : rear = rear + 1
- 원형 큐 : rear = (rear+1) % n
삭제 위치
- 선형 큐 : front = front + 1
- 원형 큐 : front = (front + 1) % n
원형 큐의 구현
초기 공백 큐 생성
- 크기 n인 1차원 배열 생성
- front와 rear을 0으로 초기화
cQ = [0]*n
front = rear = 0
공백/포화 검사
- 공백 : front = rear
- 포화
- 삽입할 rear의 다음 위치 == 현재 front
- (rear+1)%n == front
def isEmpty():
return front == rear
def isFull():
return (rear+1) % len(cQ) == front
삽입 : enQueue(item)
- 마지막 원소 뒤에 새로운 원소 삽입
- rear 값 조정해 새로운 원소 삽입 자리 마련
- rear = (rear+1)%n
- 해당 인덱스에 해당하는 배열원소 cQ[rear]에 item 저장
def enQueue(item):
global rear
if isFull():
print("Queue_Full")
else:
rear = (rear+1) % len(cQ)
cQ[rear] = item
삭제 : deQueue(), delete()
- 가장 앞에 있는 원소 삭제
- front 값 조정하여 삭제 자리 준비
- 새로운 front 원소 return
def deQueue():
global front
if isEmpty():
print("Queue_Empty")
else:
front = (front+1) % len(cQ)
return cQ[front]
우선순위 큐(Priority Queue)
- 우선순위를 가진 항목들을 저장하는 큐
- FIFO 순서가 아니라 우선순위대로 나간다.
Linked List사용배열또는리스트를 이용해 구현
우선순위 큐 적용 분야
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- OS의 테스크 스케줄링
우선순위 큐의 구현 : 배열
- 배열을 이용하여 자료 저장
- 원소 삽입 시 우선순위를 비교하여 적절한 위치에 삽입
문제점
- 삽입이나 삭제 연산이 일어날 때 원소의 재배치 발생
- 배열을 사용하기 때문
- 이에 소요되는 시간과 메모리 낭비가 큼
큐의 활용 : 버퍼(Buffer)
- 데이터를 한 곳에서 다른 한 곳으로 전송하는동안 일시적으로 그 데이터를 보관하는 데이터 영역
- 버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작
버퍼의 자료 구조
- 일반적으로 입출력 및 네트워크와 관련된 기능 이용
- 순서대로 입력/출력/전달되어야 하므로 FIFO 방식 자료구조인 큐 사용
BFS
- 너비 우선 탐색(BFS; Breadth First Search)
- 탐색 시작점의 인접한 정점들을 모두 차례로 방문, 이후 정점을 시작점으로 다시 인접한 정점 차례로 방문
- 인접한 정점들에 대해 탐색 후 다시 반복해야 하므로, FIFO가 적합
BFS의 구현 1 : 방문 체크
- dequeue A
- A를 방문한 것으로 표시(visited에 표시)
- A의 인접점 enqueue
def BFS(G, v, n):
visited = [0]*(n+1) # n : 정점의 개수
queue = [] # 큐 생성
queue.append(v) # 시작점 v를 큐에 삽입
while queue: # 큐가 비어있지 않는 동안
t = queue.pop(0) # 큐의 첫 원소 dequeue
if not visited[t]: # 방문하지 않은 곳이면
visited[t] = True # 방문한 것으로 표시
pass # 정점 t에서 할 일 코드
for i in G[t]: # t와 연결된 모든 정점에 대해
if not visited[i]: # 방문하지 않은 곳이라면
queue.append(i) # 큐에 삽입
BFS의 구현 2 : 최단경로 계산
방문한 노드를 visited에 체크하는 것에 그치는 것이 아니라, 깊이에 따라 몇 번째 이동해서 방문하는지 이동 횟수까지 체크
def BFS(G, v, n):
visited = [0]*(n+1) # n : 정점의 개수
queue = [] # 큐 생성
queue.append(v) # 시작점 v를 큐에 삽입
visited[v] = 1 # ⭐ 시작점을 1그룹으로 표시
while queue: # 큐가 비어있지 않는 동안
t = queue.pop(0) # 큐의 첫 원소 dequeue해서 t로 지정
# if not visited[t]: 필요가 없음
# visited[t] = True
pass # 정점 t에서 할 일 코드
for i in G[t]: # t와 연결된 모든 정점에 대해
if not visited[i]: # 방문하지 않은 곳이라면
queue.append(i) # 큐에 삽입
visited[i] = visited[t] + 1 # 부모 그룹의 번호보다 1 증가한 것을 넣음
visited[i] = visited[n] + 1 의 코드를 써주는 것은 단순히 i번 인덱스의 노드에 visited를 True로 표시하는 2진수 방식이 아니라, 최초 시작 노드를 1로 표시한 것으로부터 1을 더해서 2번 그룹을 만들어 주는 것. 1번 노드의 인접 노드는 2번 그룹, 이후 2번 그룹의 각 노드들에 대해 인접한 노드들을 또 3번 그룹으로 지정.
모든 검색이 끝난 후 visited 배열에는 출발점으로부터의 최단 이동 횟수가 위치한다.
번외 : Deque
from collection import deque
Q = deque()
for i in range(1000000):
Q.append(i)
while Q:
Q.popleft() # 가장 앞을 빼는 pop하는 것
- collection 패키지의 deque모듈
- double ended queue
- append와 pop, popleft 메서드를 손쉽게 사용하지만 연산시간이 빠른 것이 특징
번외 : DFS VS BFS
공통점
- 시작점에서 경로가 존재하는 모든 정점 방문 가능
- 경로 유무를 묻는 문제 DFS, BFS 모두 가능
- 결합 컴포넌트(connected component)를 찾는 문제
- 최단경로 탐색 문제 : BFS가 유리, DFS는 원래 알고리즘을 일부 수정해 해결
차이점
- DFS : 출발점에서 경로가 있는 임의 정점을 처음 방문할 때 최단으로 방문한다는 보장 X
- BFS
- 처음 방문할 때 항상 최단으로 방문
- 가중치가 부여된 그래프에서는 제한
