DFS / BFS

그래프 탐색 알고리즘 : DFS / BFS

 

 

탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다.

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다.

DFS / BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 합니다.

 

DFS 와 BFS 알고리즘을 알아보기 전에 반드시 숙지해야할 두가지 자료구조와 재귀 함수가 있다.

 

1. 스택(stack) 자료구조

- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입니다.

- 간단하게 삽입(insert), 삭제(delete) 연산이 있는데 삽입하면 제일 끝에 쌓이고, 삭제하면 제일 뒤에 있는 데이터부터 삭제된다.

python으로는 간단하게 리스트를 이용하면 된다.

stack = []

 

stack.append(5) # 삽입 5 -> [5]

stack.append(3) # 삽입 3 -> [5,3]

stack.pop() # 삭제 -> [5]

 

2. 큐(queue) 자료구조

- 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다.

- 큐도 마찬가지로 삽입(insert), 삭제(delete) 연산이 있는데 삽입하면 제일 끝에 쌓이고, 삭제하면 제일 앞에 있는 데이터부터 삭제된다.

python으로 간단하게 리스트를 이용해도 되고, deque를 이용해도 된다.

하지만 비용적으로 deque를 이용하는게 시간복잡도적으로 빠르기 때문에, deque를 이용

q = []

 

q.append(5) # 삽입 5 -> [5]

q.append(3) # 삽입 3 -> [5,3]

q.pop(1) # 삭제 -> [3]

 

from collections import deque

queue = deque()

 

queue.append(5) # 삽입 5 -> [5]

queue.append(3) # 삽입 3 -> [5,3]

queue.append(8) # 삽입 8 -> [5,3,8]

queue.popleft() # 삭제 -> [3,8]

 

 

3. 재귀 함수(recursive function)란 자기 자신을 다시 호출하는 함수를 의미

- 재귀 함수는 우리가 실질적으로 bfs dfs를 구현하고자 할때 자주 사용되는 방법중 하나이므로 꼭 이해해야 한다.

- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

- 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.

ex)

def recursive_function(i):

if i == 100:

return

print(i, '번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출')

recursive_function(i+1)

print(i,'번째 재귀 함수를 종료합니다.')

 

recursive_function(1)

 

 

 

이제 본론으로 들어가 DFS(depth-first search)를 알아보자

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

- DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리하고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

* 만약 그래프 구조를 어떻게 만들고 싶은지 알고 싶다면 참고 (https://boysboy3.tistory.com/139?category=859376)

* 어떻게 동작하고 간단한 코드를 어떻게 작성하는지 알고싶다면 참고 (https://blog.naver.com/wpghks7/221598474816) - 잘 나와있다..

 

 

# simple 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)

 

 

# 그래프가 어떻게 표현되어 있는지 구조화 되어있다. 인접 리스트(adjacency list)라고 한다.

# 예를들면 0번 노드에는 암것도 연결된 노드가 없으니 1번 노드에는 2번,3,8 번 노드가 ... 이런식으로 되어 있는 리스트이다.

graph = [

[],

[2, 3, 8],

[1, 7],

[1, 4, 5],

[3, 5],

[3, 4],

[7],

[2, 6, 8],

[1, 7]

]

 

# 각 노드가 방문된 정보를 표현 (1차원 리스트) 8번까지 있지만 0노드는 사용 안하므로 9개의 list로 만든다.

visited = [False] * 9

 

# DFS 함수 호출 (시작 노드는 1번)

dfs(graph, 1, visited) # 1,2,7,6,8,3,4,5

 

 

 

 

다음으로 BFS(breadth-first search)를 알아보자

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

- BFS는 큐 자료구조를 이용하며, 다음과 같이 동작한다

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

BFS는 간선의 cost가 동일하다는(1) 가정하에 최단거리 문제를 해결할 수 있다는 점을 기억해야 한다.

 

 

# simple bfs

from collections import deque

 

# BFS method 정의

def bfs(graph, start, visited):

# 큐(queue)를 구현하기 위해 deque 라이브러리 사용

queue = deque([start])

 

# 현재 노드 방문 처리

visited[start] = True

 

# queue가 빌 때까지 반복

while queue:

# 큐에서 하나의 원소 봅아 출력

v = queue.popleft()

print(v, end=' ')

 

# 아직 방문하지 않은 인접한 요소들을 큐에 삽입

for i in graph[v]:

if not visited[i]:

if not visited[i]:

queue.append(i)

visited[i] = True

 

 

 

graph = [

[],

[2, 3, 8],

[1, 7],

[1, 4, 5],

[3, 5],

[3, 4],

[7],

[2, 6, 8],

[1, 7]

]

 

 

# 방문된 정보 표

visited = [False] * 9

 

# BFS 함수 호출 (시작 노드는 1번)

bfs(graph, 1, visited) # 1,2,7,6,8,3,4,5

 

 

그 외 문제를 더 풀어보고 싶다면 

얼음 얼려 먹기

미로 탈출

 

위 내용들은 이코테 youtube 및 책을 참고하였습니다

이코테 링크

책 링크