[Algorithm 이론] DFS/BFS
그래프 탐색하기 위한 대표적인 두 가지 알고리즘
- 탐색(search) : 많은 양의 데이터 중 원하는 데이터를 찾는 과정
- 대표적인 탐색 알고리즘이 DFS/BFS
[자료구조(Data structure)의 기초]
: 데이터를 표현하고 관리하고 처리하기 위한 구조
- 스택과 큐는 자료구조의 기초 개념으로 아래 두 핵심적인 함수로 구성
- 삽입(push) : 데이터를 삽입한다.
- 삭제(pop) : 데이터를 삭제한다.
1. 스택(Stack)
- 선입후출 or 후입선출 구조
- 먼저 들어간게 늦게 나온다.
- 예시: 박스 쌓기
아래에서부터 위로 쌓고 아래 박스를 치우기 위해 위에 박스를 먼저 내려놔야 함
- 별도의 라이브러리 사용 X
- append()와 pop() 메서드 이용하면 됨
스택 예제
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
- stack.pop() 했을 때 어떤 것이 지워지는지 확인
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() # 7 삭제
stack.append(1)
stack.append(4)
stack.pop() # 4 삭제
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
[5, 2, 3, 1]
[1, 3, 2, 5]
2. 큐(Queue)
- 선입선출 구조
- 먼저 들어간게 먼저 나간다.
- 예시: 대기 줄
놀이공원 줄 설 때, 먼저 온 사람이 먼저 들어감 - 따라서, 공정한 자료구조라고 비유
- collections 모듈에서 제공하는 deque 자료구조 활용
- 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적
큐 예제
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
- queue.popleft() 했을 때 어떤 것이 지워지는지 확인
# 큐 구현을 위해 deque 라이브러리 사용
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() # 5 삭제
queue.append(1)
queue.append(4)
queue.popleft() # 2 삭제
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue)
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
3. 재귀함수(Recursive function)
- 자기 자신을 다시 호출하는 함수
- 재귀 함수의 종료 조건
- 재귀 함수를 사용할 때 종료 조건을 꼭 명시
- if문이 대표적
- 내부적으로 스택 자료구조와 동일
- 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀함수를 이용하면 간편하게 구현
- 재귀함수 사용 시 코드가 간결해 진다.
(재귀함수 예제)
- 반복적으로 구현한 방식과 재귀적으로 구현한 두 방식을 비교
- 반복문 대신 재귀함수 사용 시 코드가 더 간결
- 종료 조건 : if $n<=1$이면 return하여 함수 종료
- $n * factorial_recursive(n-1)$에서 $n-1$ 때문에 $n$ 값은 계속 작아지게 됨
# 1. 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
# 2. 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)
print(f'반복적으로 구현: {factorial_iterative(5)}')
print(f'재귀적으로 구현: {factorial_recursive(5)}')
반복적으로 구현: 120
재귀적으로 구현: 120
스택과 큐 사용 시 주의사항!
- 삽입과 삭제 외에 ‘오버플로’ 와 ‘언더플로’ 고민
- 오버플로: 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득찬 상태에서
삽입 연산 수행할 때 발생 - 언더플로: 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생
- 오버플로: 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득찬 상태에서
[DFS(Depth-Fisrt Search)]
- 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후,
다시 돌아가 다른 경로로 탐색
그래프의 기본 구조
- 노드(node, =정점(vertex)) & 간선(Edge)
- 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- 두 노드가 간선으로 연결 = 두 노드는 인접하다
그래프 표현방식 (2가지)
위와 같은 그래프가 있다고 가정.
1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 2차원 배열에 각 노드가 연결된 형태
- 파이썬에서 2차원 리스트로 구현
- 인접하지 않는 노드 -> 논리적으로 정답이 될 수 없는 값으로 초기화
- 모든 관계를 저장 -> 노드 개수가 많을수록 메모리 효율 BAD
- BUT, 정보를 얻는 속도는 빠름
(인접행렬 방식 예제)
- 인접행렬은 2차원 배열로 그래프 연결 관계를 나타난다했음
INF = 9999999 # 무한의 비용 선언
# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
[[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]
2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- 2차원 리스트 이용
- 연결된 정보만 저장 -> 메모리 효율 GOOD!
- BUT, 정보 얻는 속도 느림
(인접 리스트 예제)
- 모든 노드에 연결된 정보를 차례대로 연결 저장
# 노드 개수만큼 생성
graph = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장 - '(노드, 거리)' 형태
graph[0].append((1, 7)) # 0과 1인 노드가 인접해 있고 거리는 7이다
graph[0].append((2, 5)) # 0과 2인 노드가 인접해 있고 거리는 5이다
# 노드 1에 연결된 노드 정보 저장
graph[1].append((0, 7)) # 1과 0인 노드가 인접해 있고 거리는 7이다
# 노드 1에 연결된 노드 정보 저장
graph[2].append((0, 5)) # 2과 0인 노드가 인접해 있고 거리는 5이다
print(graph)
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
DFS 구체적인 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 다음 과정을 반복
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면
- 그 인접 노드를 스택에 넣고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 없으면
- 스택에서 최상단 노드를 꺼냄(버림)
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복
Tip!!
- 스택 자료 구조 이용
- 방문처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것
- 이를 통해, 각 노드를 한 번씩만 처리
- 코테에서 번호가 낮은 순서부터 처리하도록 명시하는 경우 종종 있기에 관행적으로
낮은 순서부터 처리하도록 구현 - DFS 문제는 재귀 함수를 이용했을 때 매우 간결하게 구현 가능
- O(N)의 시간 소요
(DFS 예제)
# v: 현재 내가 위치한 노드 번호
def dfs(graph, v, visited):
# 현재 노드 방문 처리
visited[v] = True
print(v, end = ' ') # 현재 내가 있는 곳 출력(중복안됨.)
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # visited[i]가 False 인 경우 = 방문 하지 않은 노드 일 경우
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원)
graph = [
[],
[2, 3, 8], # 노드 1과 인접한 노드 번호
[1, 7], # 노드 2와 인접한 노드 번호
[1, 4, 5], # 노드 3과 인접한 노드 번호
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
# 9는 노드 개수(1~8까지 있는데 계산할때 헷갈리지 않으려고 0번째 노드는 비워둠)
visited = [False]*9 # 처음에는 아무것도 방문하지 않은 상태로 시작
# 정의된 함수 호출
# 이러한 graph 가 들어갔을때 노드 1부터 시작할 것이고 처음에는 아무것도 방문하지 않은 상태로 시작할 것이다.
dfs(graph, 1, visited)
1 2 7 6 8 3 4 5
[BFS(Breadth-Fisrt Search)]
- 가까운 노드부터 탐색
- 큐 자료구조 이용(선입선출)
BFS 구체적인 동작 방식
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입
- 2번 과정 더 이상 수행할 수 없을 때까지 반복
Tip!!
- 큐 자료구조 이용
- deque 라이브러리 사용
- import collections from deque
- O(N)의 시간 소요
- 일반적으로 DFS보다 시간 효율성 높음
(BFS 예제)
# 라이브러리 불러오기 - BFS는 뭐다? queue 구조를 이용한다~
from collections import deque
# graph : 노드가 연결된 정보
# start : 시작 위치
# visited : 방문했는지 안했는지 체크하기 위한 리스
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
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과 인접한 노드 번호
[1, 7], # 노드 2와 인접한 노드 번호
[1, 4, 5], # 노드 3과 인접한 노드 번호
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
# 9는 노드 개수(1~8까지 있는데 계산할때 헷갈리지 않으려고 0번째 노드는 비워둠)
visited = [False]*9 # 처음에는 아무것도 방문하지 않은 상태로 시작
# 정의된 함수 호출
bfs(graph, 1, visited)
1 2 3 8 7 4 5 6
요약 정리!
| DFS | BFS | |
|---|---|---|
| 동작원리 | 스택 | 큐 |
| 구현방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
댓글남기기