[SW Intermediate] Queue

Queue 

---

Queue 의 종류

 

1) 선형 큐:

간단하고 기본적인 형태이며, 리스트로 구현한다.

 

2) 원형 큐:

선형에서 발전된 형태이며, 리스트로 구현한다.

 

3) 연결 큐:

연결리스트 형식으로 구현한다.

 

4) 우선순위 큐

---

선형 큐

선형 큐의 특징

1) 1차원 리스트를 이용한 큐

- 큐의 크기 = 리스트의 크기

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

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

 

2) 상태표현

- 초기상태 : front = rear = - 1

- 공백상태:  front = rear

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

 

---

원형 큐

1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용한다.

 

1) 원형 큐의 특징

(1) 초기 공백 상태:

- front = rear = 0

(2) Index의 순환:

- front와 rear의 위치가 리스트의 마지막 인덱스인 n-1을 가리키고 난 후 논리적인 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야 한다.

- 이를 위하여 나머지 연산자 %를 사용한다.

(3) front 변수

- 공백 상태와 포화 상태 구분을 쉽게 하기 위하여 front가 있는 자리는 사용하지 않고 항상 빈 자리로 둔다.

---

연결 큐

1) 연결 큐의 특징

(1) 단순 연결 리스트(Linked List)를 이용한 큐

- 큐의 원소: 단순 연결리스트의 노드

- 큐의 원소 순서: 노드의 연결 순서, 링크로 연결되어 있음

- front : 첫 번째 노드를 가리키는 링크

- rear: 마지막 노드를 가리키는 링크

 

2) 상태표현:

- 초기상태 : front = rear = None

- 공백상태: front = rear = None

 

---

우선순위 큐

- 우선순위를 가진 항목들을 저장하는 큐

- FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

 

1) 우선순위 큐 적용 분야

- 시뮬레이션 시스템

- 네트워크 트래픽 제어

- 운영체제의 태스크 스케쥴링

 

2) 구현

- 리스트를 이용한 우선순위 큐

- 우선 순위큐 라이브러리 사용

 

3) 리스트를 이용한 우선순위 큐의 구현

- 리스트를 이용하여 자료 저장

- 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조

- 가장 앞에 최고 우선순위의 원소가 위치하게 된다.

 

* 문제점

- 리스트를 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생

- 소요되는 시간이 많이걸림

 

* 해결책

- PriorityQueue(maxSize) 클래스 이용

- 힙 자료구조 이용

 

---

버퍼

1) 버퍼의 의미

- 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역

- 버퍼링: 버퍼를 활용하는 방식 또한 버퍼를 채우는 동작을 의미

 

2) 버퍼의 자료구조

- 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용

- 순서대로 입력/출력 전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용된다.

 

---

BFS(너비우선 탐색)

- 큐 활용

- 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 하여 다시 인접한 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

- 인접한 정점들을 탐색한 후 차례로 너비우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용

- 알고리즘

 

# 그래프 g, 탐색 시작점 v
def bfs(g, v):
	visited = [0] * n # n: 정점의 개수
    queue = [] # 큐 생성
    queue.append(v) # 시작점 v를 큐에 삽입
    
    while queue: # 큐가 비어있지 않은 경우
    	t = queue.pop(0) # 큐의 첫 번째 원소 반환
        if not visited[t]: # 방문되지 않은 곳이라면
        	visited[t] = True # 방문한 것으로 표시
            for i in g(t): # t와 연결된 모든 노드에 대해
            	if not visited[i]: # 방문되지 않은 곳이라면 
                	queue.qppend(i) # 큐에 넣기

 

---

문1) 회전

from collections import deque

T = int(input())
for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    num_list = list(map(int, input().split()))
    queue = deque(num_list)

    for i in range(M):
        num = queue.popleft()
        queue.append(num)

    print(f'#{test_case} {queue.popleft()}')

 

문2) 미로의 거리

from collections import deque

'''
bfs:
가까운 노드부터 탐색하는 너비 우선 탐색 알고리즘(dfs 는 최대한 멀리있는 노드 우선 탐색)

장점:
1) 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단경로임을 보장한다.
2) 노드의 수가 적고 깊이가 얕은 해가 존재할 때 효과적이다. 
'''


d = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs():
    global queue
    visited = [[0]*n for _ in range(n)]
    while queue:
        y, x = queue.popleft()
        for dx, dy in d:
            ry = y + dy
            rx = x + dx
            if 0 <= ry < n and 0 <= rx < n:
                if miro[ry][rx] == 3:
                    return visited[y][x]
                if not miro[ry][rx] and visited[ry][rx] == 0:
                    visited[ry][rx] = visited[y][x] + 1
                    queue.append((ry, rx))
                    miro[ry][rx] = 1
                    continue

    return 0

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    queue = deque()
    miro = [list(map(int,input())) for _ in range(n)]

    for y in range(n):
        for x in range(n):
            if miro[y][x] == 2:
                queue.append((y,x))
                miro[y][x] = 1
                break
    print(f'#{test_case} {bfs()}')

 

문3) 피자 굽기

from collections import deque

T = int(input())
for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    pizza = list(map(int, input().split()))
    c = deque()
    queue = deque()
    res = 0
    for i, v in enumerate(pizza):
        c.append([i+1,v])
    queue.append(c.popleft())

    while queue:
       # 화덕에 피자 넣기
       if len(queue) < n and c:
           queue.append(c.popleft())
           continue

       res = queue[0]
       l, cheese = queue.popleft()
       l, cheese = l, cheese//2

       # cheese 가 0
       if not cheese:
           continue
       else:
           queue.append([l, cheese])

    print(f'#{test_case} {res[0]}')

 

문4) 노드의 거리

# bfs 문제 푸는 방법 익히기

from collections import deque

def bfs(start_node):
    queue = deque()
    queue.append(start_node)
    visited[start_node] = 1

    while queue:
        start_node = queue.popleft()
        for node in range(1, v+1):
            if graph[start_node][node] and not visited[node]:
                queue.append(node)
                visited[node] = 1
                distance[node] = distance[start_node] + 1
                if node == end_node:
                    return distance[node]
    return 0
T = int(input())
for test_case in range(1, T + 1):
    v, e = map(int, input().split())
    graph = [[0 for _ in range(v+1)] for _ in range(v+1)]
    visited = [0] * (v+1)
    distance = [0] * (v+1)

    for _ in range(e):
        start, end = map(int, input().split())
        graph[start][end] = 1
        graph[end][start] = 1

    start_node, end_node = map(int, input().split())

    print(f'#{test_case} {bfs(start_node)}')