그래프 탐색 알고리즘 DFS/BFS
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 코테에 자주 등장하는 유형이다
스택
후입선출
stack = [] # 리스트로 구현하면 된다.
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack[::-1]) # [1,3,2,5] # 마지막에 들어간 것부터 출력
print(stack) # [5,2,3,1] # 처음 들어간 것부터 출력큐
선입선출
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용. (리스트를 사용하는 것보다 낫다)
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft() # 5,2,3,7,1,4 순으로 들어오고, 먼저 들어온 5,2가 빠진다
print(queue) # deque([3,7,1,4])
queue.reverse() # 역순으로 바꾸기
print(queue) # deque([4,1,7,3])재귀함수(recursive function)
- 자기 자신을 다시 호출하는 함수
- 함수의 정의 내에 똑같은 이름의 함수를 넣는다.
- 파이썬은 메모리 때문에 재귀호출의 제한이 있다.
- 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 넣어야 한다.
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 함
if i == 100:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)# for문을 이용하여 팩토리얼 구하기
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
# 재귀적으로 n! 구하기
def factorial_recursive(n):
# n이 1 이하인 경우 1을 반환
if n <= 1:
return 1
# n! = n * (n-1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n-1)
print('반복적으로 구현:', factorial_iterative(5)) # 120
print('재귀적으로 구현:', factorial_recursive(5)) # 120최대공약수를 구하는 '유클리드 호제법'
두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합시다.
이 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
B와 R을 다시 A', B'으로 본다면 재귀로 최대공약수를 도출할 수 있습니다.
즉, 유클리드 호제법의 아이디어를 재귀함수로 작성할 수 있습니다.
def gcd(a, b):
if a%b == 0: # a가 b의 배수(나머지가 0)라면, b를 반환한다.
return b
else:
return gcd(b, a%b) # 아니라면 호제법을 반복한다.
print(gcd(192, 162)) # 6- 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다.
DFS (Depth-First Search)
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- DFS는 스택 자료구조(or 재귀함수) 를 이용하며, 구체적인 동작 과정은 다음과 같다
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
# DFS 정의
def dfs(graph, v, visited):
# 현재 노드를 방문처리. 방문하면 True
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # not False = True, visited[i]가 False(미방문)이면 dfs 재귀호출
dfs(graph, i , visited)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[], # index대로 직관적으로 사용하기 위해 0은 비워놓는다.
[2,3,8], # 여기 입력된 순서대로 진행된다 2 -> 3 -> 8
[1,7], # 1 -> 7
[1,4,5], # 1 -> 4 -> 5 ...
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트) 미방문을 False로 함
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5 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() # v는 삽입된 순서대로 천천히 빠진다.
print(v, end=' ')
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]: # 해당 v에 들어있는 모든 원소를 queue에 삽입한다. 그리고 방문한 것으로 친다.
if not visited[i]: # 여기서 방문하지 않은 노드를 모두 큐에 넣는다.
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[], # index대로 직관적으로 사용하기 위해 0은 비워놓는다.
[2,3,8], # 여기 입력된 순서대로 진행된다 2 -> 3 -> 8
[1,7], # 1 -> 7
[1,4,5], # 1 -> 4 -> 5 ...
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트) 미방문을 False로 함
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6 
성실하고 꼼꼼하게