[이코테] DFS/BFS

1 꼭 필요한 자료구조 기초

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

자료구조 Data Structure : 데이터를 표현하고 관리하고 처리하기 위한 구조

자료구조에는 스택, 큐가 있다. 스택과 큐는 삽입, 삭제의 함수로 구성된다.

• 삽입(Push) : 데이터를 삽입한다.
• 삭제(Pop) : 데이터를 삭제한다.

 

스택(Stack)

아래에서 위로 차곡차곡 쌓는 자료구조이다. 위에서부터 꺼내기 때문에 선입후출(First In Last Out)구조 또는 후입선출(Last In First Out) 구조라고 한다.

 

파이썬에서는 리스트와 append(), pop() 메서드를 이용해서 스택 자료구조를 만들 수 있다.

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

 

 

 

큐(Queue)

나중에 온 사람이 나중에 들어가기 때문에 선입선출(First In First Out) 구조라고 한다.

 

파이썬으로 큐를 구현할 때는 collectioins 모듈에서 제공하는 deque 자료구조를 활용하면 된다.

deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용할 수 있다.

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

 

 

재귀함수

자기 자신을 다시 호출하는 함수이다.

함수의 종료 조건을 꼭 명시해야 한다. 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있다.

def recursive_function(i):
  # 10번째 출력했을 때 종료되도록 종료 조건 명시
  if i == 10:
    return
  print(i, '번째 재귀 함수에서 ', i + 1, '번째 재귀 함수를 호출합니다.')
  recursive_function(i + 1)
  print(i, '번째 재귀 함수를 종료합니다.')


recursive_function(1)

 

 

 

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 따라서 스택 자료구조를 활용해야 하는 알고리즘은 재귀 함수를 이용해서 간편하게 구현할 수 있다.

 

 

재귀 함수를 이용하는 대표적 예제로는 팩토리얼 문제가 있다. n! = 1 * 2 * 3 * … * (n-1) * n

for을 사용해서 반복적으로 구현할 수도 있고, 재귀 함수를 이용해서 구현할 수도 있다.

# 반복적으로 구현한 n!
def factorial_iterative(n):
  result = 1
  # 1부터 n까지의 수를 차례대로 곱하기
  for i in range(1, n+1):
    result *= i
  return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
  if n <= 1: # n이 1 이하인 경우 1을 반환
    return 1
  # n! = n * (n-1)!을 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)

 재귀 함수를 이용하면 반복문으로 코드를 짜는 것보다 더 간단하다.

 

 

---

2 탐색 알고리즘 DFS/BFS

DFS

Depth-First Search, 깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 이용한다.

 

DFS 의 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

'방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

노드를 방문하는 순서는 1, 2, 7, 6, 8, 3, 4, 5이다.

 

DFS는 스택 자료구조에 기초하기 때문에 구현이 간단하다. 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.

또한 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]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

 

 

BFS

Breadth First Search, 너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘이다. 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

BFS 의 동작 과정

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

 

노드를 탐색하는 순서는 1, 2, 3, 8, 7, 4, 5, 6이다.

 

deque 라이브러리를 사용하는 것이 좋으며, 수행하는데 O(N)의 시간이 소요된다. 일반적인 경우 수행 시간은 DFS보다 좋은 편이다.

 

 

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

 

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 더 쉽게 풀이가 떠오를 수 있다. 코딩 테스트에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민해보자!