DFS(깊이 우선 탐색) - 탐색하는 원소를 따라 깊이 탐색하는 것입니다.
스택, 재귀로 구현할 수 있습니다.
DFS 구현 코드입니다.
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3],
}
def dfs_recursive(node, visited):
# 방문처리
visited.append(node)
# 인접 노드 방문
for adj in graph[node]:
if adj not in visited:
dfs_recursive(adj, visited)
return visited
def dfs_stack(start):
visited = []
# 방문할 순서를 담아두는 용도
stack = [start]
# 방문할 노드가 남아있는 한 아래 로직을 반복한다.
while stack:
# 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
top = stack.pop()
visited.append(top)
# 인접 노드를 방문한다.
for adj in graph[top]:
if adj not in visited:
stack.append(adj)
return visited
BFS(너비 우선 탐색) - 탐색하는 원소에 인접한 값을 찾는 것 입니다.
큐로 구현할 수 있습니다.
BFS 구현 코드입니다.
from collections import deque
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3],
}
def bfs_queue(start):
visited = [start]
q = deque([start])
while q:
node = q.popleft()
for adj in graph[node]:
if adj not in visited:
q.append(adj)
visited.append(adj)
return visited
assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]
'파이썬 알고리즘 인터뷰 > 스터디 과제' 카테고리의 다른 글
1주차 스터디 (0) | 2024.01.07 |
---|