λνμ μΈ νμ μκ³ λ¦¬μ¦μΈ DFS / BFSλ₯Ό μ΄ν΄, ꡬννκΈ° μν΄ μ°μ μ€νκ³Ό ν μλ£κ΅¬μ‘°μ λν΄ κ°λ¨ν μμλ³΄κ² μ΅λλ€.
μ€ν - Stack
μ€νμ λ°μ€λ₯Ό μκ³ λ΄λ¦¬λ μ리μ κ°μ΅λλ€.
λ¨Όμ λ€μ΄μ¨ κ²μ΄ λμ€μ λκ°κ³ (FILO), λμ€μ λ€μ΄μ¨ κ²μ΄ λ¨Όμ λκ°λ (LIFO) ꡬ쑰μ λλ€.
λ§μ½ 1-3-5-7
μμλ‘ λ€μ΄μλ€λ©΄, 7-5-3-1
μ μμλ‘ λκ°κ² λ©λλ€.
νμ΄μ¬μμλ λ³λμ λΌμ΄λΈλ¬λ¦¬ μ¬μ©μμ΄ κΈ°λ³Έ 리μ€νΈμμ append()
μ pop()
λ©μλλ‘ λ¦¬μ€νΈλ₯Ό μ€νμ²λΌ μ¬μ©ν μ μμ΅λλ€.
append()
λ©μλλ λ°μ΄ν°λ₯Ό 리μ€νΈ κ°μ₯ λ€μͺ½μ μ½μ
νκ³ , pop()
λ©μλλ λ°μ΄ν°λ₯Ό 리μ€νΈμ κ°μ₯ λ€μͺ½μμ κΊΌλ΄κΈ° λλ¬Έμ
λλ€.
ν - Queue
νλ μ€μ μλ μ리μ κ°μ΅λλ€.
λ¨Όμ λ€μ΄μ¨ κ²μ΄ λ¨Όμ λκ°κ³ (FIFO), λμ€μ λ€μ΄μ¨ κ²μ΄ λμ€μ λκ°λ (LILO) ꡬ쑰μ λλ€.
λ§μ½ 1-3-5-7
μμλ‘ λ€μ΄μλ€λ©΄, 1-3-5-7
μ μμλ‘ λκ°κ² λ©λλ€.
νμ΄μ¬μμλ collections
λͺ¨λμμ μ 곡νλ deque
μλ£κ΅¬μ‘°λ₯Ό νμ©ν΄ νλ₯Ό ꡬνν μ μμ΅λλ€.
append()
λ©μλλ‘ λ°μ΄ν°λ₯Ό μ½μ
νκ³ , popleft()
λ©μλλ₯Ό ν΅ν΄ λ¨Όμ λ€μ΄κ° λ°μ΄ν°λ₯Ό κΊΌλ
λλ€.
from collections import deque
queue = deque()
queue.append(1)
queue.append(3)
queue.popleft()
DFS
DFSλ κΉμ΄ μ°μ νμ μκ³ λ¦¬μ¦μΌλ‘, μ΅λν κΉμν λ ΈλκΉμ§ λ°©λ¬Έν ν λ€μ λ€λ₯Έ κ²½λ‘λ₯Ό νμνλ μκ³ λ¦¬μ¦μ λλ€.
DFSλ μ€νκ³Ό μ¬κ·ν¨μλ₯Ό μ΄μ©ν΄ ꡬννλ©°, κ°λ¨ν λμ νλ¦μ μλμ κ°μ΅λλ€.
- νμ μμ λ Έλ μ€νμ μ½μ , λ°©λ¬Έ μ²λ¦¬
- μ€ν μ΅μλ¨μ μ μ₯λ λ
Έλμμ λ°©λ¬Ένμ§ μμ μΈμ λ
Έλκ° μλ€λ©΄ μΈμ λ
Έλλ₯Ό μ€νμ λ£κ³ λ°©λ¬Έ μ²λ¦¬
2-1. λ°©λ¬Ένμ§ μμ μΈμ λ Έλκ° μμΌλ©΄
pop()
- 2λ² κ³Όμ μ λ°λ³΅
μ κ·Έλ¦Όκ³Ό κ°μ κ²½μ°μ κ²°κ³Όμ μΌλ‘ λ
Έλμ νμ μμλ 1β2β4β3
μ
λλ€.
νμ΄μ¬μμ DFSλ₯Ό ꡬννλ μ½λλ μλμ κ°μ΅λλ€.
def dfs(graph, v, visited):
visited[v] = True
result.append(v)
for idx in graph[v]:
if not visited[idx]:
dfs(graph, idx, visited):
result = []
graph = [
[],
[2, 3],
[1, 4],
[1],
[2]
]
visited = [False] * len(graph)
dfs(graph, 1, visited)
BFS
BFSλ λλΉ μ°μ νμ μκ³ λ¦¬μ¦μΌλ‘, κ°κΉμ΄ λ ΈλλΆν° μ λΆ νμνλ μκ³ λ¦¬μ¦μ λλ€.
BFSλ νλ₯Ό μ΄μ©ν΄ ꡬννλ©°, κ°λ¨ν λμ νλ¦μ μλμ κ°μ΅λλ€.
- νμ μμ λ Έλλ₯Ό νμ μ½μ , λ°©λ¬Έ μ²λ¦¬
- νμμ λ Έλλ₯Ό κΊΌλ΄ ν΄λΉ λ Έλμ μΈμ λ Έλ μ€ λ°©λ¬Ένμ§ μμ μΈμ λ Έλλ₯Ό λͺ¨λ νμ μ½μ , λ°©λ¬Έ μ²λ¦¬
- 2λ² κ³Όμ μ λ°λ³΅
μ κ·Έλ¦Όκ³Ό κ°μ κ²½μ°μ κ²°κ³Όμ μΌλ‘ λ
Έλμ νμ μμλ 1β2β3β4
μ
λλ€.
νμ΄μ¬μμ BFSλ₯Ό ꡬννλ μ½λλ μλμ κ°μ΅λλ€.
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
result.append(v)
for idx in graph[v]:
if not visited[idx]:
queue.append(idx)
visited[idx] = True
result = []
graph = [
[],
[2, 3],
[1, 4],
[1],
[2]
]
visited = [False] * len(graph)
dfs(graph, 1, visited)
Uploaded by N2T