728x90
DFS(깊이 우선 탐색)
- 재귀 함수를 이용해 구현
- 시작 노드에서부터 출발해 한 방향으로 최대한 깊게 탐색한 후, 다른 방향의 노드를 탐색
- 스택 또는 재귀 호출을 통해 구현
- 모든 노드를 방문하고자 할 때 사용
def dfs(graph, start, visited=None):
# 방문한 노드들을 저장할 집합을 초기화
if visited is None:
visited = set()
# 현재 노드를 방문한 것으로 표시하고, 방문한 노드 집합에 추가
visited.add(start)
# 현재 노드를 출력
print(start) # 방문한 노드 출력
# 현재 노드의 이웃 노드들을 탐색
for neighbor in graph[start]:
# 이웃 노드가 방문한 적이 없다면 재귀적으로 방문
if neighbor not in visited:
dfs(graph, neighbor, visited)
BFS(너비 우선 탐색)
- 큐를 이용해 구현
- 시작 노드에서부터 인접한 모든 노드를 탐색한 후, 그 다음 레벨의 노드를 탐색
- 너비(수평)을 우선으로 탐색
- 최단 경로를 찾거나 노드 간의 최단 거리를 구할 때 사용됨.
from collections import deque
def bfs(graph, start):
# 방문한 노드들을 저장할 집합을 초기화
visited = set()
# 큐를 초기화하고 시작 노드를 추가
queue = deque([start])
# 시작 노드를 방문한 것으로 표시
visited.add(start)
# 큐가 빌 때까지 반복
while queue:
# 큐에서 노드를 꺼내옴
vertex = queue.popleft()
# 꺼낸 노드를 출력
print(vertex) # 방문한 노드 출력
# 꺼낸 노드의 이웃 노드들을 탐색
for neighbor in graph[vertex]:
# 이웃 노드가 방문한 적이 없다면 방문 표시하고 큐에 추가
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
728x90
반응형
'Algorithm' 카테고리의 다른 글
[프로그래머스] 종이 자르기 - 파이썬 (0) | 2024.04.15 |
---|---|
[프로그래머스] OX퀴즈 - 파이썬 (0) | 2024.04.15 |
[코딩테스트] 코딩테스트 빈출 유형 정리 (0) | 2024.04.07 |
[프로그래머스] 삼각형의 완성 조건 (2) - 파이썬 (0) | 2024.04.05 |
[프로그래머스] 영어가 싫어요 - 파이썬 (0) | 2024.04.05 |