파이썬 DFS, BFS 예시코드와 개념정리

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 25강 ~ 31강 내용 요약입니다.

 

#DFS, BFS, 백트래킹
1. 그래프(Graph) 
1.1. 그래프 실생활 예 - 지도, 네비게이션, 노선도, SNS 관계도, VCS(버전관리 시스템)
- 지하철 노선도를 예로, 그래프에서는 각 역을 Vertex(=node)라고 하고 연결선을 edge 라고 한다.
- 그리고 Vertex(=node)를 V 또는 N개, edge를 E 또는 M개라고 주로 표현한다.
1.2. 그래프 종류1 - 무방향(양방향) 그래프, 방향 그래프
1.3. 그래프 종류2 - 순환 그래프(Cyclic Graph), 비순환 그래프(Acyclic Graph)
1.4. 그래프 종류3 - 방향성 비순환 그래프(Directed Acyclic Graph) - git 그래프 등 버전관리시스템
1.5. 연결 요소 - Connected Component
- 하나의 그래프에서 연결요소가 N개일 수 있음

2. 트리 : 순환성이 없는 무방향 그래프
2.1. 특정하지 않는 한 어떤 노드든지 루트가 될 수 있다
2.2. 가장 바깥쪽 노드는 리프노드
2.3. node A 에서 node B 로 가는 경로는 반드시 존재하며 유일하다
2.4. 노드개수 = 간선개수 + 1
2.5. 자료구조에서의 트리는 부모 -> 자식 관계가 있는 방향 그래프이다.
2.6. 루트 root 는 하나다.

3. 코드로 그래프를 나타내는 방법
3.1. 인접행렬
- 행은 시작 인덱스, 열은 도착 인덱스를 의미
3.2. 인접리스트
- 시작 인덱스의 노드를 N개의 도착 인덱스의 노드로 연결
3.3. 인접행렬 vs 인접리스트
- 비교 : 
- 공간복잡도 : O(N^2) vs O(N*M) - 인접행렬은 모든 경우에서 N^2 만큼의 메모리 공간을 차지하는 반면 인접 리스트는 간선 수가 적을 수록 적은 공간을 차지함
- 검색시간 : O(1) vs O(N) - 인접행렬은 임의 접근이 가능한 반면 인접 리스트는 불가능하다.

 

# DFS 
# Depth First Search
# 스택 or 재귀를 사용해서 구현한다
# 

adj = [[0]*13 for _ in range(13)]
adj[0][1] = adj[0][7] = 1
adj[1][2] = adj[1][5] = 1
# ...
# for row in adj:
# print(row)

def dfs(now):
    for nxt in range(13):
        if adj[now][nxt]:
            dfs(nxt)

dfs(0)

# BFS
# Breath First Search
# 큐를 사용해서 구현한다
#

from collections import deque

adj = [[0]*13 for _ in range(13)]
adj[0][1] = adj[0][2] = 1
adj[1][3] = adj[1][4] = 1
# ...
# for row in adj:
# print(row)

def bfs():
    dq = deque()
    dq.append(0)
    while dq:
        now = dq.popleft()
        for nxt in range(13):
            if adj[now][nxt]:
                dq.append(nxt)

bfs()

4. DFS & BFS 공통점과 차이점
4.1. 공통점 - 그래프 탐색, 완전탐색 알고리즘임
4.2. 차이점 - DFS보다 BFS가 최단경로 알고리즘에 적합함
4.3. 인접행렬 시간복잡도: O(V^2)
4.4. 인접리스트 시간복잡도: O(V+E), O(max(V, E))