Queue & BFS

그래프 탐색 대표 알고리즘 DFS / BFS

• 탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 코테에서 매우 자주 등장하는 유형

---

Queue

• 입구와 출구가 모두 뚫려있는 터널과 같은 형태
• FIFO(First In First Out) 구조 : 먼저 들어온 데이터가 먼저 나가는 선입선출 형식의 자료구조

컨베이어 벨트처럼 들어온대로 나가는 구조!

EX ) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

⇒ 5 2 3 7 1 4

 

• List 자료형을 이용해 기능적으로는 큐를 구현할 수 있음
• But, List는 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있음
  • 만약 pop()으로 원소를 꺼내면 그 후에 나머지 원소들의 위치를 조정해줘야 하기 때문에 O(k)만큼의 시간복잡도가 요구됨
• deque는 스택과 큐 라이브러리의 장점을 합쳐놓은 자료구조

from collections import deque
# collections 모듈에서 deque 함수만 쓰겠다.

# queue 구현을 위해 deque 라이브러리 활용
queue = deque()

# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

# 넣은 순서대로 queue list 출력 = 출구에 가까운 순
print(queue)
# 데크 없이 리스트 형태만 출력하고 싶다면
print(list(queue))

# 나중에 들어온 원소부터 출력
queue.reverse()
print(queue)

deque([3, 7, 1, 4])
[3, 7, 1, 4]
deque([4, 1, 7, 3])

• 큐의 append()와 popleft()의 시간복잡도는 O(1). 상수시간

---

BFS(Breadth-First Search) : 깊이우선탐색

BFS : 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS 특징

• 큐 자료구조를 이용함
• 루트 노드나 시작 정점에서 출발해 가장 가까운 인접 노드를 먼저 모두 방문한 뒤, 넓게 퍼져나가며 탐색하는 그래프/트리 탐색 알고리즘
• DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 BFS는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있음
• 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프에서는 시작점에서 끝점까지의 최단경로를 알아낼 수 있음

from collections import deque

def bfs(graph, start, visited) :
    queue = deque([start])
    visited[start] = True
    while queue :
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v] :
            if not visited[i] :
                # print(f"\n방문하지 않은 {i} 추가")
                queue.append(i)
                visited[i] = True

graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9
# print(visited)

bfs(graph,1,visited)

1 2 3 8 7 4 5 6

 

 

 

 

재귀 함수(Recursive Function)

참고 : 동빈나 DFS & BFS