탐색 유형 - BFS/DFS

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

탐색 유형 문제 푸는 법 - 대표적인 탐색 알고리즘 DFS와 BFS를 이용

DFS와 BFS를 제대로 이해하려면 기존 자료구조인 스택,  큐, 재귀함수를 알아야한다.

 

그래프는 노드와 간선으로 표현되며

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다.

 

BFS, 너비 우선 탐색

 

가까운 노드부터 탐색하는 알고리즘이다.

BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용한다.('큐에서 꺼낸 노드'의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 하기때문에 큐 자료구조를 이용해야 한다.)

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

from collections import deque

# bfs 함수 정의
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 visited[i]:
            	queue.append(i) # (꺼낸 노드의 인접 노드 중에서)방문하지 않은 노드들을 모두 큐에 삽입
                visited[i] = True # (꺼낸 노드의 인접 노드 중에서)방문 처리를 한다.

 

BFS는 O(N)의 시간이 소요되며 수행 시간은 DFS보다 좋다.

 

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

 

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

실제 구현에는 스택을 쓰지 않아도 되지만 스택 자료구조에 기초하기 때문에 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

 

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

 

DFS는 O(N)의 시간이 소요된다.

 

출처 : 이것이 ~ 코딩 테스트다 with 파이썬