탐색 알고리즘 - DFS / BFS

Tip 탐색문제는 그래프 형태로 표현 후 풀이하면 좋다.

DFS : Depth-First Search, 깊이 우선 탐색

1. 인접 행렬 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록
   • 연결되지 않은 노드는 무한의 비용이라고 작성
   • 장점 : 모든 관계를 저장하므로 메모리가 불필요하게 낭비된다.
   • 단점 : 인접 리스트 방식에 비해 속도가 빠르다
2. 인접 리스트 방식 : 모든 노드에 연결된 노드에 대한 정보를 차례로 연결하여 저장
   • 장점 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
   • 단점 : 연결된 데이터를 하나씩 확인해야하므로 속도가 느리다.

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

graph = [
	..
	생략
	..]
	

visited = [False] * 9

dfs(graph, 1, visited)

BFS: Breadth-First Search, 너비 우선 탐색

• 가까운 노트부터 탐색
• 선입선출인 queue 자료구조를 이용하는 것이 정석
• 파이썬에서 deque 라이브러리를 사용해서 구현
• O(N)의 시간복잡도를 가진다. DFS 보다 수행시간은 좋은 편이다.

from collections import deque

def bfs(graph, start, visited):
	queue = deque(start)
	visited[start] = True #현재 노드를 방문 처리

	while queue:
		v= queue.popleft() #popleft : 첫번째 원소 제거 
		print(v, end=' ')

		for i in graph[v]:
			if not visited[i]:
				queue.append(i) #해당 원소와 연결된 아직 방문하지 않은 원소들은 삽입
				visited[i] = True			

graph = [
	..
	생략
	..]

visited = [False] * 9

bfs(graph, 1, visited)