[Python] 기본 탐색 - 완전탐색, DFS/BFS

Outline

---

1. 완전탐색
2. DFS/BFS

---

완전탐색(브루트 포스)

• 모든 경우의 수를 탐색
• 전체 데이터 개수가 100만 개 이하일 때 사용

DFS/BFS

• 그래프 탐색 알고리즘
• 재귀함수의 수행은 스택 자료구조 이용
• 스택, 큐 관련 기초지식
• 그래프 관련 기초지식

DFS(깊이 우선 탐색)

• 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색
• 스택 자료구조에 기초(선입후출)
• 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결
• 시간복잡도 O(N) 

def dfs(graph, v, visited):
	visitied[v] = True
    print(v, end ='')
    for i in graph[v]:
    	if not visitied[i]:
        	dfs(graph, i, visited)
        
graph =[
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)

BFS(너비 우선 탐색)

• 가까운 노드부터 탐색
• 큐 자료구조에 기초(선입선출)
• 시간복잡도 O(N) - 실제 수행시간은 DFS보다 좋은 편

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
    	print(v, end='')
    	for i in graph[v]:
    		if not vistied[i]:
        		queue.append(i)
                visited[i] = True

 

코딩테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각해보자!

 

참고

[책] 이것이 취업을 위한 코딩 테스트다