3. DFS & BFS

📌 1. 스택과 큐 자료구조

1. 스택 - list

stack = []

stack.append(1)
stack.append(2)
stack.pop()
stack.append(3)
stack.append(4)
stack.append(5)

print(stack[::-1]) # 최상단 원소부터 출력 # [5, 4, 3, 1]
print(stack) # 최하단 원소부터 출력 # [1, 3, 4, 5]

2. 큐 - from collections import deque

• list로도 구현 가능하지만 deque의 연산 속도가 더 빠르니까 deque 사용 추천

from collections import deque

queue = deque()

queue.append(1) # queue의 오른쪽에 원소 삽입
queue.append(2)
queue.popleft() # queue의 왼쪽에서 원소 삭제
queue.append(3)
queue.append(4)
queue.append(5)

print(queue) # 먼저 들어온 원소부터 출력 # deque([2, 3, 4, 5])
queue.reverse()
print(queue) # 나중에 들어온 원소부터 출력 # deque([5, 4, 3, 2])

📌 2. 재귀 함수

• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임

• 스택 - 재귀 함수

📌 3. DFS 알고리즘

• DFS - 스택 - list - 재귀 함수

def dfs(graph, v, visited):
  # 방문 처리
  visited[v] = True
  print(v, end = ' ')

  # 인접 노드 처리
  for i in graph[v]:
    if not visited[i]: # 방문하지 않은 인접 노드일 경우
      dfs(graph, i, visited)

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

visited = [False] * 9

dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

📌 4. BFS 알고리즘

• BFS - 큐 - from collections import deque

• 가까운 노드부터 우선 탐색

• 최단 거리

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]: # 방문하지 않은 인접 노드일 경우
        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

bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6

---

[참고]

• (이코테 2021 강의 몰아보기)3. DFS & BFS (https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3)