DFS/BFS 이론 (큐&스택)

그래프 탐색 알고리즘 (DFS/BFS)

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘은 DFS/BFS
• 코딩 테스트에서 자주 등장하는 유형

---

먼저 2가지 큐랑 스택의 기본 구조를 알고 있어야한다.

<스택 자료구조>

출처 : 이코테 2021

<스택 구현 예제>

stack = []
#삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1])
print(stack)

#실행 결과
[1, 3, 2, 5]
[5, 2, 3, 1]

파이썬에서는 표준라이브러리 없이 스택을 구현할 수 있다.

<큐 자료구조>

 

<큐 구현 예제>

from collections import deque

#큐 구현을 위한 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()

print(queue) #먼저 들어온 순서
queue.reverse()
print(queue)#역순

#실행 결과
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])

.append는 가장 오른쪽

.popleft는 가장 왼쪽을 꺼낸다.