[SWEA] [파이썬 SW 문제해결 기초] 5. Queue

[Queue]

- 삽입(큐 뒤), 삭제(큐 앞)의 위치가 제한적인 자료구조
- 선입선출(FIFO)

※ 큐의 주요 연산

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

※ 큐 종류
- 선형 큐: 리스트 사용
- 원형 큐: 리스트 사용
- 연결 큐: 연결 리스트 형식 사용
- 우선순위 큐: 큐를 응용

 

[Queue의 종류]

1. 선형 queue
- 보통 1차원 리스트를 이용하여 구현 (큐의 크기 = 리스트의 크기)
- front: 저장된 첫 번째 원소의 인덱스 / rear: 저장된 마지막 원소의 인덱스
- 초기 상태: front = rear = -1 (비어 있어서 저장된 원소가 없음)
- 공백 상태: front = rear (큐의 연산이 진행되는 동안 큐가 비어있는 상태)
- 포화 상태: rear = n-1 (n: 리스트의 크기, n-1: 리스트의 마지막 인덱스) => 큐 가득 차 있음

구현
초기 createQueue() : 초기 공백큐 생성	크기가 n인 1차원 리스트 생성 front, rear = -1로 초기화
enQueue(item) : 원소 삽입	마지막 원소 뒤에 새로운 원소를 삽입하기 위해: 1) rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련 2) 그 인덱스에 해당하는 리스트원소 Q[rear]에 item을 저장
deQueue() : 원소 삭제	가장 앞에 있는 원소를 삭제하기 위해: 1) front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소로 이동함 2) 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능을 함
isEmpty(), isFull() : 공백상태 및 포화상태 검사	공백상태: front = rear 포화상태: rear = n-1
Qpeek() : 맨 앞 원소 검색	가장 앞에 있는 원소를 검색하여 반환 현재 front의 한 자리 뒤(front+1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소 반환

def enQueue(item):
  global rear
  if isFull():
    print("Queue_Full")
  else:
    rear += 1
    Q[rear] = item
    

def deQueue():
  global front
  if isEmpty():
    print("Queue_Empty")
  else:
    front += 1
    return Q[front]
    

def isEmpty():
  return front == rear

def isFull():
  return rear == len(Q)-1
  
def Qpeek():
  if isEmpty():
    print("Queue_Empty")
  else:
    return Q[front+1]

 

2. 원형 queue
- 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용함
- 초기 공백 상태: front = rear = 0
- 리스트의 마지막 인덱스 n-1을 가리킨 후 다시 처음 인덱스 0으로 돌아감 => 나머지 연산자 % 사용
- front가 있는 자리는 사용하지 않고 항상 빈자리로 둠

테이블 인덱스	삽입 위치	삭제 위치
선형 큐	rear = rear + 1	front = front + 1
원형 큐	rear = (rear + 1) % n	front = (front + 1) % n

구현
초기 createQueue() : 초기 공백큐 생성	크기가 n인 1차원 리스트 생성 front, rear = 0으로 초기화
isEmpty(), isFull() : 공백상태 및 포화상태 검사	공백상태: rear = front 포화상태: 삽입할 rear의 다음 위치 = 현재 front => (rear + 1) % n = front
enQueue(item) : 원소 삽입	마지막 원소 뒤에 새로운 원소를 삽입하기 위해: 1) rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련: rear = (rear + 1) % n 2) 그 인덱스에 해당하는 리스트원소 cQ[rear]에 item을 저장
deQueue(), delete() : 원소 삭제	가장 앞에 있는 원소를 삭제하기 위해: 1) front 값을 조정하여 삭제할 자리를 준비함 2) 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능을 함

def isEmpty():
  return front == rear
 
def isFull():
  return (rear+1) % len(cQ) == front
  
def enQueue(item):
  global rear
  if isFull():
    print("Queue_Full")
  else:
    rear = (rear+1) % len(cQ)
    cQ[rear] = item
    
def deQueue():
  global front
  if isEmpty():
    print("Queue_Empty")
  else:
    front = (front+1) % len(cQ)
    return cQ[front]
    
def delete():
  global front
  if isEmpty():
    print("Queue_Empty")
  else:
    front = (front+1) % len(cQ)		# 지우기만 하는군.

3. 리스트 특성을 사용한 queue
- 크기를 동적으로 변경 가능 => 메모리 절약
- 삽입, 삭제 시 복사, 데이터 이동 연산 수행에 많은 시간 소모
- append(item), pop(index) 사용
- front: 리스트의 맨 앞 = -1 / rear: 리스트의 맨 뒤 = len(queue) - 1

4. 연결 queue
- 단순 연결 리스트를 이용
- 큐의 원소: 단순 연결 리스트의 노드
- 큐의 원소 순서: 노드의 연결 순서, 링크로 연결되어 있음
- front: 첫 번째 노드를 가리키는 링크 / rear: 마지막 노드를 가리키는 링크
- 초기 상태/공백 상태: front = rear = None
- 포화 상태 존재 X

구현
초기 createLinkedQueue() : 초기 공백큐 생성	리스트 노드 없이 포인터 변수만 생성 front, rear = None으로 초기화
isEmpty() : 공백상태 검사	공백상태: rear = front = None
enQueue(item) : 원소 삽입	1) 새로운 노드 생성 후 데이터 필드에 item 저장 2) 연결 큐가 공백인 경우, 아닌 경우에 따라 front 및 rear 변수 지정
deQueue() : 원소 삭제	1) old 변수가 지울 노드를 가리키게 하고, front 재설정 2) 삭제 후 공백 큐가 되는 경우, rear도 None으로 설정 3) old가 가리키는 노드를 삭제하고 메모리 반환

# 초기 공백 큐 생성
front = None
rear = None

def isEmpty():
  return front == None
 
def enQueue(item):	# 연결 큐의 삽입 연산
  global front, rear
  newNode = Node(item)	# 새로운 노드 생성
  if isEmpty():	# 큐가 비어있다면
    front = newNode
  else:
    rear.next = newNode
  rear = newNode
  
def deQueue():	# 연결 큐의 삭제 연산
  global front, rear
  if isEmpty():
    print("Queue_Empty")
    return None
  item = front.item
  front = front.next
  if isEmpty():
    rear = None
  return item

※ 파이썬: 큐 모듈 존재
queue.Queue(maxsize): 선입선출 큐 객체 생성
queue.LifoQueue(maxsize): 후입선출 큐 객체 생성
queue.PriorityQueue(maxsize): 우선순위 큐 객체 생성
- 입력되는 아이템 형식: (순위, 아이템)의 튜플
- 숫자가 작을 수록 높은 우선순위

 

[Queue의 활용]

1. 우선순위 Queue
- 우선순위를 가진 항목들을 저장하는 큐
- FIFO 순서 X, 우선순위가 높은 순서대로 먼저 나감
- 리스트 이용하거나 라이브러리 사용 가능
- enQueue(삽입): 우선순위가 맞는 위치에 삽입
- deQueue(삭제): 우선순위가 가장 높은, 가장 앞의 원소 삭제
- 가장 앞: 최고 우선순위 원소 위치

2. 버퍼로도 활용 가능

 

★[BFS (너비 우선 탐색)]

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

# 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		# 방문한 것으로 표시
      visit(t)
    for i in G[t]: 		# t와 연결된 모든 선에 대해
      if not visited[i]:	# 방문되지 않은 곳이라면
        queue.append(i)		# 큐에 넣기

# queue가 비어있으면 탐색 종료

 

---

 

5097. N개의 숫자로 이루어진 수열이 주어진다. 맨 앞의 숫자를 맨 뒤로 보내는 작업을 M번 했을 때, 수열의 맨 앞에 있는 숫자를 출력하는 프로그램을 만드시오.

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    idx = M % N
    answer = arr[idx]
    print(f"#{test_case} {arr[idx]}")

당황스러울 정도로 쉬운 문제. 사실 queue 안 쓰고 하기는 했지만 그만큼 간단한걸...?

 

5105. NxN 크기의 미로에서 출발지 목적지가 주어진다. 이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오. 경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다. 

# DFS 사용 #

def rootFind(x, y, distance):
    global answer

    if maze[x][y] == 3:
        if answer > distance:
            answer = distance - 1		# 0의 개수만 세는데, distance엔 목적지도 포함되어 있어서
        return
    
    for dx, dy in movement:
        nx = x+dx
        ny = y+dy
        if (0<=nx<=N-1) and (0<=ny<=N-1):
            if not visited[nx][ny] and maze[nx][ny] != 1:
                visited[nx][ny] = True
                rootFind(nx, ny, distance+1)
                visited[nx][ny] = False

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    maze = [list(map(int, input().strip())) for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:
                start_x = i
                start_y = j
                break
	
    visited = [[False] * N for _ in range(N)]
    movement = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    answer = 100

    rootFind(start_x, start_y, 0)

    result = answer if answer != 100 else 0
    print(f"#{test_case} {result}")

기존의 미로 탈출 문제에서 살짝 변형한 것 같아서 그냥 백트래킹으로 풀었다.(테스트케이스 10개 중 1개 틀린 건 비밀)
BFS로 안 풀어서 생긴 문제인 것 같아서 BFS로도 풀어보려고 했으나, 공부의 부족... 구현 어떻게 하는지 모르겠는걸...
유튜브에서 DFS, BFS 간단하게 관련 강의 들었는데, 근데 둘다 그래프 탐색 알고리즘이라 더 잘 맞는 문제 유형은 있을 수 있어도 어쨌든 결과는 나온다고 했다. 뭐야 그럼 이거 왜 안 풀림?

# 최종 코드 #
def rootFind(x, y, distance):
    global answer

    if maze[x][y] == 3:
        if answer > distance:
            answer = distance
        return
    
    for dx, dy in movement:
        nx = x+dx
        ny = y+dy
        if (0<=nx<=N-1) and (0<=ny<=N-1):
            if not visited[nx][ny] and maze[nx][ny] != 1:
                visited[nx][ny] = True
                
                # 통로일 때만 칸 수가 증가함
                if maze[nx][ny] == 0:
                    rootFind(nx, ny, distance + 1)
                else:
                    rootFind(nx, ny, distance)
                visited[nx][ny] = False

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    maze = [list(map(int, input().strip())) for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:
                start_x = i
                start_y = j
                break

    visited = [[False] * N for _ in range(N)]
    visited[start_x][start_y] = True		# 시작 지점 방문 표시하기!
    movement = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    answer = float('inf')		# 큰 수는 float('inf')로 사용하자.. 임의의 큰 수 말고.

    rootFind(start_x, start_y, 0)

    result = answer if answer != float('inf') else 0
    print(f"#{test_case} {result}")

0(통로)일 때만 distance + 1을 하고 그 외의 경우는 그냥 재귀하도록 코드를 수정했다. 그래서 원래 'if maze[x][y] == 3' 문에 있었던 'answer = distance - 1'도 'answer = distance'로 수정해줬다.
그리고 오류가 났던 가장 중요한 부분이 answer를 임의의 큰 수로 설정해야 했는데 그냥 100이라는 딱 정해진 정수를 사용해서 그런 것이었다. 앞으로는 float('inf')를 쓰도록 하자.

+) 번외로, visited에 무조건 시작지점도 방문했다는 표시 넣는 거 잊지 말기!!

 

5099. N개의 피자를 동시에 구울 수 있는 화덕이 있다. 피자는 치즈가 모두 녹으면 화덕에서 꺼내며, 치즈의 양은 피자마다 다르다. 1번부터 M번까지 M개의 피자를 순서대로 화덕에 넣을 때, 치즈의 양에 따라 녹는 시간이 다르기 때문에 꺼내지는 순서는 바뀔 수 있다. 주어진 조건에 따라 피자를 구울 때, 화덕에 가장 마지막까지 남아있는 피자 번호를 알아내는 프로그램을 작성하시오.

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())
    tmp_pizza = list(map(int, input().split()))		# 각 피자의 치즈 (이 뒤에서 사용 X)
    pizza_cheese = [[i+1, p] for i, p in enumerate(tmp_pizza)]		# 피자랑 치즈 같이 저장
    fire = pizza_cheese[:N]	    # 화덕에 들어가는 피자
    remain = pizza_cheese[N:] 		# 남아있는 피자
    
    while len(fire) > 1:		# 피자 개수가 1개보다 많아야 함
        cheese_state = fire.pop(0)		# 불 속에 있는 치즈의 현황 ex. 1 7
        if cheese_state[1] // 2 != 0:		# 7을 2로 나눴을 때
            cheese_state[1] = cheese_state[1] // 2
            fire.append(cheese_state)       # 다시 화덕에 피자 넣어주기
        else:		# 2로 나눠 떨어짐 = 치즈 다 녹았을 때
            if remain:		# 남은 피자 있으면
                fire.append(remain.pop(0))
                
    print(f"#{test_case} {fire[0][0]}")

 

5102. V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다. 주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오.

'''
무방향 그래프
V: 노드 개수, E: 간선 개수
Q. 최소 몇 개의 간선을 지나야 도착 노드에 갈 수 있음?
'''
from collections import deque

def bfs(start, end):
    queue = deque()
    queue.append([start, 0])
    visited = [False] * (V+1)
    visited[start] = True
    
    while queue:
        current, depth = queue.popleft()
        if current == end:      # 목적지에 도달
            return depth
        
        for i in range(1, V+1):
            if arr[current][i] and not visited[i]:      # 경로가 있고, 방문하지 않음
                queue.append([i, depth+1])
                visited[i] = True
    return 0

T = int(input())
for test_case in range(1, T+1):
    V, E = map(int, input().split())
    arr = [[False] * (V+1) for _ in range(V+1)]
    
    for _ in range(E):
        i, j = map(int, input().split())
        arr[i][j] = True        # 무방향 그래프니까 둘다 표시
        arr[j][i] = True
    
    S, G = map(int, input().split())
    
    answer = bfs(S, G)
    print(f"#{test_case} {answer}")