728x90
그래프 탐색 알고리즘 : DFS / BFS
- 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
- 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다.
스택(Stack)
- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
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)
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
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) # 나중에 들어온 원소부터 출력
데크(deque)
- 스택과 큐의 특징을 혼합한 자료구조이다.
- 데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
from collections import deque
deq = deque()
# Add element to the start
deq.appendleft(10)
# Add element to the end
deq.append(0)
# Pop element from the start
deq.popleft()
# Pop element from the end
deq.pop()
재귀함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수를 의미한다.
- 재귀함수를 문제 풀이에서 사용할 때는 종료 조건을 반드시 명시해야한다.
- 종료조건을 제대로 명시하지 않으면 함수가 무한히 호출 됨
# 반복적으로 구현한 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)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
유클리드 호제법 - 최대공약수 계산
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
재귀함수 유의사항
- 복잡한 알고리즘을 간결하게 작성할 수 있지만, 다른사람이 이해하기 어려운 코드가 될 수 있음.
- 모든 재귀함수는 반복문으로 동일한 기능을 구현할 수 있다.
- 재귀함수가 반복문보다 유리할수도, 불리할 수도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이기 때문에 스택을 사용해야할 때 스택 대신 재귀를 이용하는 경우가 많다.
DFS(Depth- First Search)
- 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- 검색 속도 자체는 너비우선탐색(BFS)보다 느림
- DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 아래와 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문처리 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
# 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는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘인다.
- 큐 자료구조를 이용하며, 구체적인 동작과정은 아래와 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 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, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
DFS/BFS 구분
- 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하나, 문제별로 더 빠른 방법이 존재함
- 그래프의 모든 정점을 방문하는것이 주요한 문제 단순히 모든 정점을 방문하는 문제는 DFS, BFS 둘 중 편한것을 사용하면 됨
- 경로의 특징을 저장해둬야하는 문제 예를 들면 각 정점에 숫자가 적혀있도, a부터 b까지 가는 경로를 구하는데 같은 숫자가 있으면 안된다는 문제 들, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용하는것이 좋음(BFS는 경로의 특징을 가지지 못함)
- 최단거리 구해야하는 문제 미로찾기 등 최단거리를 구해야할 경우, BFS가 유리 왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드에서 가까운곳부터 찾기때문에 경로 탐색시 먼저 찾아지는 해답이 곧 최단거리이다.
- 이밖에 검색 대상 그래프가 엄청 크다면 DFS 고려 검색 대상 규모가 안크고, 시작지점으로부터 원하는 지점이 멀지 않으면 BFS 고려
728x90
'코딩테스트' 카테고리의 다른 글
| BFS&DFS_심화15) 특정 거리의 도시 찾기 _ python (0) | 2023.09.25 |
|---|---|
| 백트래킹(Backtracking) (1) | 2023.09.25 |
| 구현_심화13) 치킨 배달 _ python (0) | 2023.09.25 |
| 구현_심화12) 기둥과 보 설치 (0) | 2023.09.25 |
| 구현_심화9) 문자열 압축 (0) | 2023.09.25 |