728x90
함께 푼 문제
깊이 우선 탐색 (DFS)
그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
- 시간 복잡도 : O(V + E)
- 재귀함수 또는 스택으로 구현 가능
- 그래프는 보통 인접 리스트로 나타냄
- 인접 리스트 : 그래프를 표현하기 위한 방법 중 하나. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법.
- 노드 방문 여부 체크리스트(visited) 필요
파이썬 구현 : 재귀함수
def DFS(v):
visited[v] = True
print(v)
for i in A[v]:
if not visited[i]:
DFS(i)
넓이 우선 탐색 (BFS)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
- 시간 복잡도 : O(V + E)
- 큐로 구현 가능
- 그래프는 보통 인접 리스트로 나타냄
- 노드 방문 여부 체크리스트(visited) 필요
- 경로가 여러 개일 때 최단 경로를 보장
파이썬 구현
def BFS(v):
q = deque()
q.append(v)
visited[v] = True
while q:
n = q.popleft()
print(n)
for i in A[n]:
if not visited[i]:
q.append(i)
visited[i] = True
반응형
'알고리즘 > Do it! 알고리즘 코딩테스트 (파이썬)' 카테고리의 다른 글
[10, 11일차] 06 그리디 (0) | 2024.04.04 |
---|---|
[9일차] 05 탐색 : 05-3 이진 탐색 (1) | 2024.04.01 |
[7일차] 04 정렬 : 04-5 병합 정렬, 04-6 기수 정렬 (1) | 2024.04.01 |
[6일차] 04 정렬 : 04-3 삽입 정렬, 04-4 퀵 정렬 (0) | 2024.04.01 |
[5일차] 04 정렬 : 04-1 버블 정렬, 04-2 선택 정렬 (0) | 2024.03.24 |