깊이우선탐색(DFS)/너비우선탐색(BFS)

탐색(Search)이란?

- 많은 양의 데이터 중에서 원하는 데이터를  찾는 과정

- 대표적인 그래프 탐색 알고리즘으로는 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있음

- DFS/BFS는 코딩테스트 빈출유형이므로 반드시 숙지해야 함

 

DFS(Depth-First Search)란?

- 깊이우선탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 자료구조(혹은 재귀함수)를 사용

- 동작 과정

1. 탐색 시작 노드를 스택에 push, 방문 처리
2. 스택 최상단에 방문하지 않은 인접한 노드가 있으면 push, 방문 처리(단, 방문하지 않은 노드가 없으면 pop)
3. 더 이상 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)


visited_s = [False] * 9
graph_s = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

dfs(graph_s, 1, visited_s)

BFS(Breadth-First Search)란?

- 너비우선탐색이라고도 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조 이용

- 동작 과정

1. 탐색 시작 노드를 큐에 push, 방문 처리
2. 큐에서 노드를 pop, 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 push하고 방문처리
3. 더 이상 2. 의 과정을 수행할 수 없을 때까지 반복

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 visited[i]:
                queue.append(i)
                visited[i] = True


visited_s = [False] * 9
graph_s = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

bfs(graph_s, 1, visited_s)