BFS / DFS

대표 문제 유형

• 경로 탐색 (최단 거리, 시간)
  • 최단 거리 : BFS
  • 경로의 가짓수(경우의 수) : DFS
• 네트워크 (연결)
• 조합 (모든 조합 만들기)

 

구현 방법

• DFS : Stack, 재귀함수
• BFS : Queue, LinkedList

 

무방향 그래프

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
	# 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠
graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

 

---

DFS (Depth First Search)

• DFS를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문’한다고 가정함
• 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

# DFS 메서드 정의
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
	visited[v] = True
	print(v, end=' ')
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
	# 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠
graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

# 정의된 dfs 함수 호출
dfs(graph, 1, visited)  # 실행 결과: 1 2 7 6 8 3 4 5

실행 결과: 1 2 7 6 8 3 4 5

 

---

BFS (Breadth First Search)

• 간선의 비용이 동일한 상황에서 최단 거리를 구하기 위한 목적으로 사용
• 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드를 방문 처리
	visited[start] = True
	# 큐가 빌 때까지 반복
	while queue:
		# 큐에서 하나의 원소를 뽑아 출력하기
		v = queue.popleft()
		print(v, end=' ')
		# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

# 정의된 dfs 함수 호출
bfs(graph, 1, visited)  # 실행 결과: 1 2 3 8 7 4 5 6

실행 결과: 1 2 3 8 7 4 5 6

 

 

 

 

---

참고:

https://www.youtube.com/watch?v=BsYbdUnKZ-Y&t=85shttps://www.youtube.com/watch?v=BsYbdUnKZ-Y&t=85s

https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2402s