💡 Algorithm
Algorithm - [ DFS / BFS ]
date
Jun 19, 2023
slug
algorithm-01
author
status
Public
tags
Python
Algorithm
summary
그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
type
Post
thumbnail
category
💡 Algorithm
updatedAt
Jul 28, 2023 07:04 AM
DFS (Depth-First Search)
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS 는 어떻게 작동할까?
DFS 는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
⇒ 깊이 우선 탐색이라는 이름에서부터 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인하면 된다.
DFS 는 스택 자료 구조에 기초한다는 점에서 구현이 간단하다. 그런데 코드를 보면 스택을 쓰지 않고 재귀 함수로 구현을 한다.
이유는 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용하기 때문이다.
다음의 예시를 보자.
def recursive_function(i): # 100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.') recursive_function(i + 1) print(i, '번째 재귀함수를 종료합니다.') recursive_function(1)
컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다.
⇒ 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현할 수 있다.
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차원 배열 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)
⇒ 1 2 7 6 8 3 4 5
BFS (Breadth-First Search)
너비 우선 탐색이라는 의미를 가지며, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘
(DFS 는 최대한 멀리 있는 노드를 우선 탐색하는 방식으로 동작)
BFS 는 어떤 방식으로 구현할 수 있을까?
선입선출 방식인 큐 자료 구조를 이용하여 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
BFS 구현 예제
# queue 구현을 위해 deque 라이브러리 사용 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 # 각 노드가 연결된 정보 2차원 배열 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보 visited = [False] * 9 # 함수 호출 bfs(graph, 1, visited)
⇒ 1 2 3 8 7 4 5 6
Tip : 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각해 보자.
(출처: 이것이 코딩 테스트다)