[Python] [알고리즘] 6. 큐

큐

큐는 FIFO(선입선출) 구조로, 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다.

front : 저장된 원소 중 첫번째 원소

rear : 저장된 원소 중 마지막 원소

큐의 기본 연산

삽입은 enQueue, 삭제는 deQueue라고 부른다.

연산	기능
enQueue(item)	큐의  뒤쪽에 원소를 삽입하는 연산
deQueue()	큐의 앞쪽에서 원소를 삭제하고 반환하는 연산
createQueue()	공백 상태에서 큐를 생성하는 연산
isEmpty()	큐가 공백상태인지를 확인하는 연산
isFull()	큐가 포화상태인지를 확인하는 연산
Qpeek()	큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산

선형 큐

1차원 배열을 이용한 큐

큐의 크기가 배열의 크기가 된다.

- front : 저장된 첫 번째 원소의 인덱스

- rear : 저장된 마지막 원소의 인덱스

상태 표현

초기 상태:  front = rear = -1

공백 상태: front == rear

포화 상태: rear == n-1(n: 배열의 크기, n-1: 배열의 마지막 인덱스)

포화 상태의 경우 front가 관여하지 않는다. rear만 관여한다. front가 관여하지 않기 때문에 실제로 큐가 다 차지 않아도 포화 상태라고 착각할 수 있다.

초기 공백 큐 생성

• 크기가 n인 1차원 배열 생성
• front와 rear를 -1로 초기화

삽입

• 마지막 원소 뒤 새로운 원소를 삽입하기 위해 rear값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련한다. 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장한다.

삭제

• 가장 앞의 원소를 삭제하기 위해 front값을 하나 증가시켜 큐에 남아있게 될 첫 번째 원소 이동시킨 후, 새로운 첫 번째 원소를 리턴하여 삭제와 동일한 기능을 한다.

잘못된 포화상태 인식

선형 큐를 이용해서 삽입과 삭제를 계속할 경우, 사용할 수 있는 공간이 있는데도 불구하고 포화상태라고 인식해 삽입을 수행하지 않는 문제가 발생한다.

해결방안 1) 매 연산이 이루어질 때마다 원소들을 배열의 앞부분으로 이동시킨다. 원소 이동에 너무 많은 시간이 소모되어 큐의 효율성이 떨어진다.

해결방안 2) 1차원 배열을 사용하되, 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용한다.

원형 큐

초기 공백 상태는 front = rear = 0이다.

원형 큐에서는 front와 rear의 위치가 n-1을 가리킨 후, 배열의 처음 인덱스인 0으로 이동해야 한다. 이를 위해 나머지 연산자 mod를 사용한다.

원형 큐에서는 공백 상태와 포화 상태가 자칫 헷갈리기 쉽기 때문에, 이를 구별하기 위해서 front가 있는 자리는 사용하지 않고 빈자리로 둔다.(N-1개의 공간만을 채운다.)

	삽입 위치	삭제 위치
선형 큐	rear = rear +1	front = front +1
원형 큐	rear = (rear+1)mod n	front = (front+1) mod n

우선 순위 큐

우선 순위 큐의 특성

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

버퍼

한 곳에서 데이터를 다른 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역. 버퍼를 활용하는 방식이나 버퍼를 채우는 동작을 버퍼링이라고 한다.

버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용된다. 순서대로 입력/출력/전달되어야 하니 FIFO 방식의 자료구조인 큐가 활용된다.

BFS

BFS는 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 다시 인접한 정점을 차례대로 방문하는 방식. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, FIFO인 큐를 이용한다.

def bfs(G,v,n): #그래프 G와 시작점 v가 들어온다.
    visit = [0] * (n+1)
    queue= []
    queue.append(v) #시작점 v를 큐에 삽입
    visit[v] = 1 #시작점 방문 표시(인큐되었음을 표시)
    while queue:
        t = queue.pop(0)
        visit(t) #탐색 목적에 맞는 일 해주기. #문제에서 원하는 연산 수행
        for i in G[t]:
            if not visit[i]:
                queue.append(i)
                visit[i] = visit[n]+1 #n으로부터 1까지 이동

코드블럭의 맨 마지막 라인에 있는 visit[i] = visit[n]+1은 A-B로 이동할 때 visit[A]에서 1을 더하는 것을(인접한 정점이기 때문에) 의미한다. visit[i] ( 다음 블록으로 이동할 때) visit[n] +1 (원래의 visit에 1을 더하는 것을 의미)

'''
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''

def bfs(v,N): #시작점 v, 마지막 정점 번호 N
    visited = [0] * (1+N)#visited 생성
    q = [] #큐 생성
    q.append(v)#시작점 인큐
    visited[v] = 1 #visited 표시(시작점 인큐 표시)

    while q: #큐가 비어있지 않다면(큐가 빌 때까지 연산 수행)
        t=  q.pop(0)
        print(t, end=' ') #문제에서 원하는 연산 수행(t에서 처리할 일)
        for w in adjL[t]: # t에 인접이고 방문한 적 없는 w
            if visited[w] == 0:
                q.append(w) #인큐
                visited[w] = visited[t] + 1 #인큐 표시
    print(visited) #거리 정보도 알 수 있음!

V,E = map(int, input().split())
arr= list(map(int, input().split()))
adjL = [[] for _ in range(V+1)] #인접 리스트 만들기
for i in range(E):
    n1,n2 = arr[i*2], arr[i*2+1]
    adjL[n1].append(n2)
    adjL[n2].append(n1) #양방향이기 때문에

bfs(1,V) #시작 정점 1, 마지막 정점 V

dfs는 재귀로 풀 수 있지만 bfs는 재귀로 풀 수 없다. 재귀는 기본적으로 함수 호출(스택) 형태이기 때문에 큐를 이용하는 bfs를 재귀로 풀 수 없는 것.