2024-03-13 AI 코딩 TIL

오늘도 튜터님의 강의로 하루를 시작해 봅시다!

Queue를 이용한 너비우선 탐색 BFS

 

from collections import deque

큐를 사용하기 위해서 import 해주어야 하는 

순열을 구하는 방법을 재귀가 아닌 큐를 이용해서도 만들어 줄 수 있다

이때 맨처음에 1,2,3,4를 큐에 넣어주고

만들어지는 조합마다 다시 큐에 마지막에 넣어준다는 개념으로 접근을 할 수 있다.

 

BFS

 미로탐색 풀이

 

 

이 개념을 정확하게 이해하게 되었습니다.

bfs를 위해서는 큐를 주로 사용하고 dfs를 위해서는 재귀를 주로 이용한다는 말이 이제는 이해가 되더라고요...ㅎㅎ

 

BFS의 장점

최단경로 찾기가 가능하다!

전염이 되는 경우!

DFS와 달리 제일 먼저 얻어진 해가 최단경로가 된다!

가는 길이 한 가지 방법이 아닐 때 유용하다!

사람관계를 찾아갈 때

하나씩 촌수를 찾아갈 때!

 

BFS의 단점

찾아야 하는 값이 깊은 쪽에 있을 때

1. DFS에 비해 메모리가 많이 사용 될 수 있다.

2. BFS의 동작 점증이 DFS에 비해 까다로울 수 있다.

 

BFS -> 최단경로, 전염, 전이

DFS -> 

다익스트라 알고리즘!

네이게이션 최단 경로 구하는 방법 같은 곳에 사용 할 수 있습니다!

 

 

---

과제 만들기

큐(queue)에 대해

큐란??

선입선출(先入先出, First In First Out; FIFO)의 자료구조. 대기열이라고도 한다. Queue[1]라고도 하는데, Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.

- Rear와 Front

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다.)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다.)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다. 우선순위 큐, 원형 큐 등의 베리에이션이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다[2].

- 원형큐(Circular Queue)란?

큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게 된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다. 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하지만 시작과 끝이 연결되어 있다는 데서 차별성을 띤다. 링 버퍼 (ring buffer)라고 부르기도 하는데, 자료구조는 동일하지만 버퍼나 캐시 등을 목적으로 쓰는 경우 그렇게 부르는 편.

 + 앞뒤 상관 없이 아무든 먼저 들어온 것이 먼저 나간다는 점에서 그냥 queue랑 동일한 말이지 않나.... 싶다 ㅎㅎ

- 우선순위 큐 = heap??

우선순위 큐는 말 그대로 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것이다. 이 경우에 만약 우선순위가 낮은 원소가 들어간다면(Enqueue) 빼낼 때에는(Dequeue) 정말로 들어갈 땐 마음대로지만 나갈땐 아닌 상황이 된다. 대표적인 예로 heap이 있다. 

 + 한마디로 큐에 우선순위를 넣어주면 heap과 같은 개념??

 - DEQ란? = deque??

deque는 double-ended queue 의 줄임말로, 앞과 뒤, 즉, 양방향에서 데이터를 처리(삽입, 삭제) 할 수 있는 queue형 자료구조를 의미한다. python에서는 collections.deque는 리스트와 비슷하다.

  + 하지만 목적이 앞 또는 뒤를 빼고 넣는 다는 점에서 다른것 같습니다.

- (선택) 한 걸음 더
    - 우선 순위 큐에 대해 개념을 정리해 보세요.

 내가 생각하는 큐의 개념은 순서가 중요한 리스트라고 생각합니다. 먼저 들어온 것을 먼저 처리 함으로써
일을 처리하는 순서가 순차적으로 진행이 되는 것을 확인할 수 있으며 내가 스택은 되돌아가는 용도로 사용을 한다면 큐는 계획적이로 일을 진행 해야 할 때 사용을 하는 것 같습니다.

   - 자연스럽게 힙(Heap)과 개념을 연결할 수 있습니다.

위에서도 정리한 대로 큐와 동일하게 순서대로 일을 진행을 하다 우선순위라는 것이 주어져서 빨리 해야 하거나 작거나 큰일부터 해야 하는 조건이 들어가면 heap이 되는 것 같다는 생각이 들었습니다.

   - 물론 이 과정에서 힙(Heap) 자료구조에 대한 정리도 필요합니다.

좋은 힙 설명이 있어 참조 합니다.

•  

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

자신이 만든 큐를 사용하는 간단한 코드를 함께 작성해 주세요.

 

class MyQueue:
    def __init__(self):
        self.temp = None
        self.max_limit = 0  # 최대값 제한
        self.size = 0  # 아무것도 안설정하면 크기는 0
        self.items = []  # 내용도 비어있음
        self.able = 0  # 1 이면 limit on! 0 이면 limit off!

    def limit(self, limit):
        self.max_limit = limit  # 최대치 설정
        self.able = 1  # limit on!

    def limit_release(self):
        self.able = 0
        self.max_limit = 0

    def is_empty(self):
        if self.size == 0:  # 사이즈가 0이면 비어있는 상태 Ture
            return True
        else:
            return False  # 아니라면 False 출력

    def is_full(self):
        if self.able == 1:
            if self.size >= self.max_limit:  # size의 값이 limit 랑 같으면 꽉 참
                return True
            else:
                return False
        else:
            print("제한 설정이 없습니다.")

    def push(self, item):
        if self.able == 1:
            if self.size < self.max_limit:  # 제한 값 보다 작으면 넣음
                self.size += 1
                self.items.append(item)
            else:  # 제한 값 보다 크면 못 넣음
                print("스택이 가득 찼습니다.")
        else:
            self.size += 1
            self.items.append(item)

    def pop(self):
        if not self.is_empty():
            self.temp = self.items[-1]  # 마지막 열에 있는 값 따로 저장
            del self.items[-1]  # 마지막 열 제거
            self.size -= 1
            return self.temp  # 따로 넣어 둔 값 리턴
        else:
            print("리스트가 비어 있습니다.")

    def popleft(self):
        if not self.is_empty():
            self.temp = self.items[0]  # 가장 왼쪽 열에 있는 값 따로 저장
            del self.items[0]  # 가장 왼쪽 열 제거
            self.size -= 1
            return self.temp  # 따로 넣어 둔 값 리턴
        else:
            print("리스트가 비어 있습니다.")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 마지막 열에 있는 값 보여주기
        else:
            print("리스트가 비어 있습니다.")

    def peekleft(self):
        if not self.is_empty():
            return self.items[0]  # 마지막 열에 있는 값 보여주기
        else:
            print("리스트가 비어 있습니다.")

    def clear(self):
        self.items = []
        self.size = 0
        self.able = 0
        self.max_limit = 0

    def is_contain(self, item):
        return item in self.items # item 이 안에 있으면 참 없으면 거짓!

    def list(self):
        return self.items


# 클래스 인스턴스 설정
queue = MyQueue()
# 비어있는지 확인
print(queue.is_empty())  # True
# 가득 찾는지 확인
print(queue.is_full())  # 제한 설정이 없습니다.
# 최대 입력수 제한 2개
queue.limit(2)
print(queue.is_full())  # False
# 1 Enqueue
queue.push(1)
print(queue.is_full())  # False
# 2 Enqueue
queue.push(2)
# 2 Enqueue
queue.push(2) # 스택이 가득 찼습니다.

print(queue.is_full())  # True
# 현재 큐 표시
print(queue.list())  # [1, 2]
# 1 처음 값 Dequeue 후 a 변수에 넣기
a = queue.popleft()
print(a)  # 1
# 2 마지막 값 Dequeue 후 a 변수에 넣기
a = queue.pop()
print(a)  # 2
# 빈 리스트
print(queue.list())  # []
# 2 Enqueue
queue.push(2)
# 리스트 초기화
queue.clear()
# 리스트 확인
print(queue.list())  # []
# 1,2,3 Enqueue
queue.push(1)
queue.push(2)
queue.push(3)
# 맨 마지막 입력 값 확인
print(queue.peek())  # 3
# 맨 처음 입력 값 확인
print(queue.peekleft())  # 1
# 큐안에 1과 0의 값이 있는지 확인
print(queue.is_contain(1))  # True
print(queue.is_contain(0))  # False

 

---

문제 풀이

트럭

저는 트럭이 다리 위에 올라 갈 수 있는 기준을 만들었습니다.

1. 먼저 트럭이 진입하기 전에 다리 위에 무게가 초과가 되었는지?
2. 초과가 안되면 대기 중인 트럭에 맨 앞의 트럭을 빼서 다리 위에 queue마지막에 넣습니다.
3. 그러면  [0,0]이였던 다리 위에 [0.0,7]이 되고 맨 앞에 열을 빼주면 [0,7]이 됩니다
4. 다음 조건을 다시 들어오면 10이 초과가 되기 떄문에 else로 빠져서 [7,0]으로 만들어주고
5. 다음에 들어오는 버스가 빠지면서 들어와야 하기 때문에 다리 위에 [0]번 값을 뺀 값을 넣어주어야 합니다.
6. 그리고 마지막에 버스가 들어오면 뒤에 들어오는 트럭이 없기 때문에 더이상 비교를 쓸 필요가 없이 마지막 버스가 빠지는 거리인 w만 카운터에 더해주면 최종 시간이 나옵니다.

import sys
from collections import deque

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

# 각각 트력의 개수, 다리 길이, 최대 가능 무게
n, w, l = map(int, input().split())

# 트럭 순서 및 다리 위에 올라간 트럭 순서 표기
queue_b = deque()
queue_t = deque()

# 다리위에 올라간 트럭 표시
for _ in range(w):
    queue_b.append(0)
# 올라갈 트럭을 나누어서 큐에 입력
for i in list(map(int, input().split())):
    queue_t.append(i)

# 시간 측정
counter = 0

# 대기중인 모든 트럭이 출발하면 종료
while len(queue_t) > 0:
    # 횟수 1회 증가
    counter += 1
    # 다리 위에 트럭의 총 무게가 다리 최대 가능 무게를 넘기지 않는가? + 마지막으로 빠지는 트럭은 계산에 넣지 않는다.
    if sum(queue_b) - queue_b[0] + queue_t[0] <= l:
        # 0번 트럭 아웃
        queue_b.popleft()
        # 대기 트럭 0번 빼서 다리 마지막 줄에 추가
        queue_b.append(queue_t.popleft())
    else:
        # 다리 가능 무게 다차면 다리위에 트럭만 전진하고 빈공간 하나 채우기
        queue_b.popleft()
        queue_b.append(0)

# 마지막 대리열 트럭이 다리위에 올라갔다면 이제는 마지막트럭이 다리만 지나가면 되니 다리길이인 w만 추가 하면 된다.
print(counter + w)

 

라우터

반복문에서 조건 탈출 문으로 break를 사용했고

`print(" ".join(map(str, queue)))` 처음에는 이걸 사용했는데 
구글링으로 다른 사람의 글을 보니 

`print(*queue)` 이렇게도 사용이 가능하다는 것을 알았습니다..
꿀팁!

import sys
from collections import deque

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

# 라우터가 최대로 담을 수 있는 정보의 크기
n = int(input())
# 데이터를 담을 큐의 통
queue = deque()
# -1이 나올 때까지 계속 반복문 진행
while True:
    # 입력값 받기
    input_x = int(input())
    # -1이면 반복문 종료
    if input_x == -1:
        break
    # 0 이면 큐에 있는 맨앞의 값 제거
    if input_x == 0:
        queue.popleft()
    # 0이 아니면서 큐가 가득차지 않았다면 새로운 값 받아주기
    else:
        if len(queue) < n:
            queue.append(input_x)

# 라우터가 비었으면 empty
if len(queue) == 0:
    print("empty")
# 정보가 있다면 정보 표시 *붙이면 가능하다.
else:
    print(*queue)

 

바이러스

앞 전에 있었던 문제인 바이러스를 이번에는 queue를 이용하여 풀이를 하는 방법입니다..
먼저 그래프를 만들어주고 검사목록인 queue를 만들어 주어서 하나 씩 빼서 감염을 시키는 방법입니다.

# Code
import sys

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

from collections import deque

# 컴퓨터 및 연결 수 입력
computers = int(input())
links = int(input())
# 검사 목록 명단
queue = deque()
# 그래프를 이용 각 컴퓨터 번호에 연결 되어 있는 컴퓨터를 표시
linked_com = [[] for _ in range(computers)]
# 컴퓨터가 감염이 되어 있는지 확인 유무
infection = [0 for _ in range(computers)]

# 연결에 맞추어 각 컴퓨터에 연결 번호를 입력
for i in range(links):
    a, b = map(int, input().split())

    linked_com[a - 1].append(b - 1)
    linked_com[b - 1].append(a - 1)

# 1번 컴퓨터 즉 0번 위치에 있는 컴퓨터를 감염시키고 검사목록에 올려 놓기
infection[0] = 1
queue.append(0)

# 더이상 검사를 할게 없을 때까지 반복하기
while len(queue) > 0:
    # 검사 목록에서 하나 빼서 그 컴퓨터와 연결 되어 있는 것들 다 가져오기
    com = queue.popleft()
    # 연결 된 컴퓨터가 감염이 되어 있는지????
    for i in linked_com[com]:
        # 감염이 안되어 있는 컴퓨터라면 감염을 시키고 그 컴퓨터랑 연결 되어 있는 컴퓨터를 전부 검사 목록으로 넣는다.
        if infection[i] == 0:
            infection[i] = 1
            queue.append(i)

 

유기농 배추

이 문제를 접근 할 때 [0,0]부터 한 칸 씩 검사를 하는데 한 번이라도 배추를 만나게 되면 인접한 배추를 모두 0으로 만들어주면 다음 검사에 배추가 있던 자리도 검사를 하지 않고 지나가게 됩니다. 

처음에 문제를 풀 때에 재귀 함수를 사용해서 문제를 풀었는데 재귀 함수 초과로 런타임 에러가 발생하였습니다!.

그래서 구글링 결과 큐 방법을 사용해도 가능 하다는 것을 보고 직접 큐 방식으로 
while 반복문을 이용해서 작성을 하였습니다.

[런타임 에러 (RecursionError)](https://www.acmicpc.net/help/rte) 
이거 뜨면 dfs 말고 bfs로 접근 하는게 좋은 방법 인 것 같습니다.

# Code
import sys

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


T = int(input())
for _ in range(T):

    m, n, k = map(int, input().split())

    matrix = [[0 for _ in range(m)] for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        matrix[b][a] = 1

    counter = 0

    def solution(y, x):
        stack = [(y, x)]
        matrix[y][x] = 0
        while stack:
            y, x = stack.pop()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < m and 0 <= ny < n and matrix[ny][nx] == 1:
                    matrix[ny][nx] = 0
                    stack.append((ny, nx))


    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                counter += 1
                solution(i, j)

    print(counter)


# ---재귀------
# dx = [1, -1, 0, 0]
# dy = [0, 0, 1, -1]
# 
# 
# T = int(input())
# for _ in range(T):
# 
#     m, n, k = map(int, input().split())
# 
#     matrix = [[0 for _ in range(m)] for _ in range(n)]
# 
#     for _ in range(k):
#         a, b = map(int, input().split())
#         matrix[b][a] = 1
# 
# 
#     counter = 0
# 
#     def solution(y, x):
#         matrix[y][x] = 0
#         for i in range(4):
#             nx = x + dx[i]
#             ny = y + dy[i]
# 
#             if 0 <= nx < m and 0 <= ny < n and matrix[ny][nx] == 1:
#                 solution(ny, nx)
# 
# 
#     for i in range(n):
#         for j in range(m):
#             if matrix[i][j] == 1:
#                 counter += 1
#                 solution(i, j)
# 
#     print(counter)

 

미로 탐색

미로 탐색 할 때 x축과 y축을 혼동 하지 않도록 하자!!!
IndexError: list index out of range 자꾸 이 오류 떠서  한참 찾았는데….

`maze[ny][nx]` y축이 먼저 x축이 나중이였다…. 이거 햇깔리는 순간 바로 꼬이기 시작한다…

m이 y값이고 n이 x의 값인 것도 자주 착각하는 것 중 하나 였다… 이거는 어디에 적어 두어야 한다!!!

import sys
from collections import deque

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

# 칸수 이동
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# m이 y의 갯수 n이 x의 갯수다! 
m, n = map(int, input().split())
# n의 단어가 m줄 있습니다.
maze = [list(map(int, input())) for _ in range(m)]
# 큐 생성 = 탐험해야 할 목록
queue = deque()

# ----- 미로 확인 용 궁금 하면 주석 풀고 확인 ----
# for i in maze:
#     print(i)
# 0,0 부터 시작
queue.append((0, 0))
# 탐험 시작
while queue:
    # 탐험 목록에서 가장 먼저 해야 할 것 꺼내기
    x, y = queue.popleft()
    # 이동
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위 안이면서 값이 1인 땅 찾기
        if 0 <= nx < n and 0 <= ny < m and maze[ny][nx] == 1:
            # 탐험 목록 추가
            queue.append((nx, ny))
            # 지금 위치에 전의 값보다 1 많게 해서 값 변경
            maze[ny][nx] = maze[y][x] + 1
# 최종 목적지의 값
print(maze[m - 1][n - 1])

 

토마토

튜터님 강의에 있던 토마토를 풀어 보았습니다.

처음에 만들때 날짜 개념으로 카운트를 잡을려고 하니 문제가 있어 진행한 횟수가 가장 길었던 토마토의 길이를 최대 일로 잡고 만드니 가능했습니다.

# Code
import sys
from collections import deque

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

# 상하좌우 이동 방법
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

m, n = map(int, input().split())

tomato = [list(map(int, input().split())) for _ in range(n)]

queue = deque()


for y in range(n):
    for x in range(m):
        if tomato[y][x] == 1:
            queue.append((x, y))

while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and tomato[ny][nx] == 0:
            tomato[ny][nx] = tomato[y][x] + 1
            queue.append((nx, ny))

flag = True
max_day = 0

for i in tomato:
    if 0 in i:
        print(-1)
        flag = False
        break
    else:
        if max_day < max(i):
            max_day = max(i)

if flag:
    print(max_day - 1)