선형 큐를 이용하여 원소의 삽입/삭제를 반복하는 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 rear = n-1인 상태 즉, 포화상태로 인식하여 더이상의 데이터 삽입을 수행하지 않게 된다.
✔ 해결방법 1 매 연산(삽입/삭제)이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시키는 방법 But, 원소 이동에 많은 시간이 소요되어 큐의 효율성이 매우 떨어짐
✔ 해결방법 2 1차원 배열에 대해 논리적으로는 배열의 처음과 끝이 연결된 원형 형태의 큐를 이룬다고 가정하여 사용하는 방법
원형 큐의 논리적 구조
✅ 원형 큐의 특징
초기 공백 상태 : front = rear = 0
Index의 순환
front와 rear의 위치가 배열의 마지막 인덱스(n - 1)를 가리킨 후, 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동 -> 이를 구현하기 위해 나머지 연산자(mod)를 사용
공백 상태와 포화 상태 구분을 위해 front가 있는 자리는 항상 사용하지 않고 빈자리로 둠
✅ 선형 큐와 원형 큐의 삽입/삭제 위치
✅ 원형 큐의 연산
1. 생성: create Queue
front = rear = 0 초기화
2. 삽입: enQueue(A)
def enQueue(item):
global rear
if isFull():
print("Queue_Full")
else:
# rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련
rear = (rear + 1) % len(cQ)
# 그 인덱스에 해당하는 배열원소 cQ[rear]에 item 저장
cQ[rear] = item
# 포화상태: 삽입할 rear의 다음 위치 == 현재 front
def isFull():
# (rear + 1) mod n == front
return (rear + 1) % len(cQ) == front
3. 삭제: deQueue()
def deQueue():
global front
if isEmpty():
print("Queue_Empty")
else:
# front 값을 조정하여 삭제할 자리를 준비
front = (front + 1) % len(cQ)
# 새로운 front 원소를 리턴하여 삭제와 동일한 기능 동작
return cQ[front]
# 공백상태: front == rear
def isEmpty():
return front == rear
✅ 공백상태 및 포화상태 검사: isEmpty(), isFull()
# 공백상태: front == rear
def isEmpty():
return front == rear
# 포화상태: 삽입할 rear의 다음 위치 == 현재 front
def isFull():
# (rear + 1) mod n == front
return (rear + 1) % len(cQ) == front
# 1. 공백 큐 생성 (front = rear = 0)
createLinkedQueue()
# 2. 원소 A 삽입
enQueue(A)
# 3. 원소 B 삽입
enQueue(B)
# 4. 원소 삭제
deQueue()
# 5. 원소 삭제
deQueue() # front = rear = 0 이 됨
탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점들을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 (인접한 정점들에 대해 탐색한 후, 차례로 다시 너비우선탐색(BFS)을 진행해야 하므로, 선입선출(FIFO) 형태의 자료구조인 큐(Queue)를 활용함)
인접한 정점을 순차적으로 방문할 때에는, 데이터 값에 대해 내림차순으로 방문한다.
완전 탐색이 가능하긴 하지만, 일반적으로 DFS와 달리 완전 탐색을 실행하지 않는다는 특징을 가진다.
📌 최소 몇 번의 연산을 해야하는가에 대한 문제를 해결할 땐 항상 DFS보단 BFS가 더 적합하다! (DFS는 가지치기에 유리함)
✅ BFS의 장점
정해진 개수만큼 큐를 생성해도 충분하다.
재귀 호출에서의 장점을 가짐(강의 다시 보기..)
# G: 그래프, v: 탐색 시작점, n: 정점의 개수
def bfs(G, v, n):
visited = [0] * (n + 1)
# 큐 생성
queue = []
# 시작점 v를 큐에 삽입
queue.append(v)
# 큐가 비어있지 않는 동안
while queue:
# 큐의 첫 번째 원소를 반환 -> dequeue()
t = queue.pop(0)
# 방문하지 않은 곳인 경우,
if not visited[t]:
# 방문한 곳으로 표시해둠
visited[t] = True
# 정점 t에서 할 일 수행
visit(t)
# t와 연결된 모든 정점에 대해
for i in G[t]:
# 방문되지 않은 곳이라면
if not visited[i]:
# 큐에 넣기
queue.append(i)
def visit(n):
...
BFS의 그래프 탐색 순서
① 초기 상태
Visited 배열 초기화
Q (큐) 생성
enqueue(A)
② A 점부터 시작
dequeue()
A 점을 방문한 것으로 표시
A의 인접점을 euqueue()
③ 탐색 진행
dequeue()
B점 방문한 것으로 표시
B의 인접점을 enqueue()
dequeue()
C점 방문한 것으로 표시
C의 인접점을 enqueue()
dequeue()
D점 방문한 것으로 표시
D의 인접점을 enqueue()
이후 Q에 대해 dequeue()를 반복하며 내보내진 점을 방문한 것으로 표시하고, 해당 점의 인접점을 enqueue() 함
④ Q가 비면 탐색 종료
✅ BFS 예제
# G: 그래프, v: 탐색 시작점, n: 정점의 개수
def BFS(G, v, n):
visited = [0] * (n + 1)
# 큐 생성
queue = []
# 시작점 v를 큐에 삽입
queue.append(v)
visited[v] = 1
# 큐가 비어있지 않는 동안
while queue:
# 큐의 첫 번째 원소 반환
t = queue.pop(0)
visit(t)
# t와 연결된 모든 정점에 대해
for i in G[t]:
# 방문되지 않은 곳이라면
if not visited[i]:
# 큐에 넣음
queue.append(i)
# n으로부터 1만큼 이동
visited[i] = visited[t] + 1
💡 deque 객체 양쪽 끝에서 빠르게 추가 및 삭제를 할 수 있는 List류의 컨테이너이다.
✅ 데크 연산
from collections import deque
q = deque()
# append(x): 오른쪽에 x 요소를 추가함
q.append(1) # enqueue()
# popleft(): 왼쪽에서 요소를 제거하여 반환함 (요소가 없으면 IndexError 발생)
t = q.popleft() # dequeue()
✅ 예제
아래와 같이 시계 방향으로 1 ~ 5가 적힌 다이얼의 현재 가리키는 눈금이 1이라고 할 때, 이 다이얼을 오른쪽으로 2칸 돌려 가리키는 눈금이 4가 되도록 하려면 어떻게 해야 하는가? (출처: https://wikidocs.net/104977)
[1, 2, 3, 4, 5] → [4, 5, 1, 2, 3]
sol) 리스트(list)를 n만큼 회전하는 문제는 Python에서는 collections.deque 모듈을 사용하면 간단히 해결할 수 있다.
from collections import deque
a = [1, 2, 3, 4, 5]
q = deque(a)
q.rotate(2) #시계방향 회전은 양수, 그 반대는 음수
result = list(q)
print(result) # [4, 5, 1, 2, 3]
세 개의 데이터 1, 2, 3을 차례로 큐에 삽입하고 큐에서 세 개의 데이터를 차례로 꺼내어 출력 (1, 2, 3이 출력되어야 함)
Queue를 이용하여 마이쮸 나눠주기 시뮬레이션을 해보자.
엔터(Enter)를 칠 때마다 아래의 정보를 화면에 출력
큐에 있는 사람의 수
현재 일인당 나눠주는 사탕의 수
현재까지 나눠준 사탕의 수
마지막 마이쮸를 누가 가져가게 될지 출력해보자.
"""
- 엔터(Enter)를 칠 때마다 아래의 정보를 화면에 출력
1. 큐에 있는 사람의 수
2. 현재 일인당 나눠주는 사탕의 수
3. 현재까지 나눠준 사탕의 수
"""
import time
def isFull():
global queue
global rear
if rear == len(queue) -1 :
return True
return False
def enQueue(item):
global queue
global rear
if isFull():
print("Queue is Full now!")
else:
rear += 1
queue[rear] = item
def deQueue():
global queue
global front
global rear
if front == rear:
print("Queue is Empty now!")
else:
front += 1
return queue[front]
def pressEnter():
global front
global rear
global queue
global myChew
input("엔터를 입력해주세요.")
who = None
for i in range(front + 1, rear + 1):
who = queue[i][0]
myChew -= queue[i][1]
deQueue()
print(f'큐에 있는 사람의 수: {rear - front}')
print(f'현재 일인당 나눠주는 사탕의 수: {queue[i][1]}')
print(f'현재까지 나눠준 사탕의 수: {20 - myChew}')
print()
print('**************************************')
print()
time.sleep(0.1)
return who
myChew = 20
front = rear = 0
queue = [None] * 1000000
cnt = 1
while myChew != 0:
k = 1
n = cnt + 1
for i in range(cnt):
enQueue((k, n - k))
k += 1
who = pressEnter()
front = rear
cnt += 1
print(f'사탕을 마지막으로 가져간 사람: {who}')
# 출력 결과 엔터를 입력해주세요. 큐에 있는 사람의 수: 0 현재 일인당 나눠주는 사탕의 수: 1 현재까지 나눠준 사탕의 수: 1 **************************************
엔터를 입력해주세요. 큐에 있는 사람의 수: 1 현재 일인당 나눠주는 사탕의 수: 2 현재까지 나눠준 사탕의 수: 3
큐에 있는 사람의 수: 0 현재 일인당 나눠주는 사탕의 수: 1 현재까지 나눠준 사탕의 수: 4 **************************************
엔터를 입력해주세요. 큐에 있는 사람의 수: 2 현재 일인당 나눠주는 사탕의 수: 3 현재까지 나눠준 사탕의 수: 7
큐에 있는 사람의 수: 1 현재 일인당 나눠주는 사탕의 수: 2 현재까지 나눠준 사탕의 수: 9
큐에 있는 사람의 수: 0 현재 일인당 나눠주는 사탕의 수: 1 현재까지 나눠준 사탕의 수: 10 **************************************
엔터를 입력해주세요. 큐에 있는 사람의 수: 3 현재 일인당 나눠주는 사탕의 수: 4 현재까지 나눠준 사탕의 수: 14
큐에 있는 사람의 수: 2 현재 일인당 나눠주는 사탕의 수: 3 현재까지 나눠준 사탕의 수: 17
큐에 있는 사람의 수: 1 현재 일인당 나눠주는 사탕의 수: 2 현재까지 나눠준 사탕의 수: 19
큐에 있는 사람의 수: 0 현재 일인당 나눠주는 사탕의 수: 1 현재까지 나눠준 사탕의 수: 20 **************************************
사탕을 마지막으로 가져간 사람: 4
BFS (너비 우선 탐색)
아래는 연결되어 있는 두 개 정점 사이의 간선을 순서대로 나열해 둔 것이다. 모든 정점을 너비우선탐색(BFS)하여 경로를 출력하여라. (시작 정점은 1로 한다)
# G: 그래프, v: 탐색 시작점, n: 정점의 개수
def bfs(G, v, n):
visited = [0] * (n + 1)
# 큐 생성
queue = []
# 시작점 v를 큐에 삽입
queue.append(v)
# 큐가 비어있지 않는 동안
while queue:
# 큐의 첫 번째 원소를 반환 -> dequeue()
t = queue.pop(0)
# 방문하지 않은 곳인 경우,
if not visited[t]:
# 방문한 곳으로 표시해둠
visited[t] = True
# 정점 t에서 할 일 수행
visit(t)
# t와 연결된 모든 정점에 대해
for i in G[t]:
# 방문되지 않은 곳이라면
if not visited[i]:
# 큐에 넣기
queue.append(i)
print(t, end = ' ')
def visit(t):
pass
# 입력 데이터
input_data = '1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7'
# 7개의 노드로 구성
N = 7
# 그래프 생성
graph = [[] for i in range(N + 1)]
arr = list(map(int, input_data.split()))
for i in range(0, len(arr) - 1, 2):
v1, v2 = arr[i], arr[i + 1]
graph[v1].append(v2)
graph[v2].append(v1)
# bfs 탐색 실시
bfs(graph, 1, N)
