while문이나 for문을 사용하지 않고 자기 자신을 무한히 호출 할 수 있고,종료 조건을 사용하여 호출을 종료해야 한다.
재귀함수라도 무한히 출력하다보면 최대 재귀 깊이 초과 메시지가 출력된다.
#재귀함수 출력 종료조건문 명시
def recursive(i):
# 10번째에 호출 종료
if i == 10:
return
print(i, '번째 재귀 함수에서', i+1, '번째 재귀함수를 호출.')
recursive(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive(1)
DFS(Depth- First Search) : 깊이 우선 탐색
💡 깊이 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
그래프에서깊은 부분을 우선적으로 탐색하는 알고리즘
'스택'자료구조 또는 재귀함수를 사용한 그래프 탐색 알고리즘
가장 깊은 노드까지 도달하였을 때 탐색한 경로를 역추적하여 되돌아나오기 위해 스택을 사용
또한 이미 방문한 노드를 다시 방문하지 않기 위해 방문한 노드를 따로 저장을 해야한다. 이를'방문 처리'라고 한다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
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, 4], #1번 노드와 연결되어있는 노드들
[1, 5, 6], #2번 노드와 연결되어있는 노드들
[1], #3번 노드와 연결되어 있는 노드들
[1, 7], #4번 노드와 연결되어 있는 노드들
[2, 8], #5번 노드와 연결되어 있는 노드들
[2, 8], #6번 노드와 연결되어 있는 노드들
[4], #7번 노드와 연결되어 있는 노드들
[5, 6] #8번 노드와 연결되어 있는 노드들
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
스택을 통한 구현
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2, 3, 4], #1번 노드와 연결되어있는 노드들
[1, 5, 6], #2번 노드와 연결되어있는 노드들
[1], #3번 노드와 연결되어 있는 노드들
[1, 7], #4번 노드와 연결되어 있는 노드들
[2, 8], #5번 노드와 연결되어 있는 노드들
[2, 8], #6번 노드와 연결되어 있는 노드들
[4], #7번 노드와 연결되어 있는 노드들
[5, 6] #8번 노드와 연결되어 있는 노드들
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
#스택을 통한 DFS구현
stack.append(1)
visited[1] = True
while len(stack) > 0:
current_node = None
for node in graph[stack[-1]]:
if visited[node] == False:
current_node = node
break
if current_node == None:
stack.pop()
else:
visited[current_node] = True
stack.append(current_node)
print(visited)
탐색 순서: 1-> 2-> 5-> 8-> 6-> 3-> 4-> 7
👌 DFS를 사용하는 경우
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
BFS(Breadth- First Search) : 너비 우선 탐색
💡 깊이 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서인접한 노드를 먼저탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
현재 노드와 가까운 노드를 우선적으로 넓게 탐색하는 방식
'큐'자료구조를 사용한 그래프 탐색 알고리즘
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
BFS 코드 구현
# 그래프는 DFS 그래프와 동일
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, 4], #1번 노드와 연결되어있는 노드들
[1, 5, 6], #2번 노드와 연결되어있는 노드들
[1], #3번 노드와 연결되어 있는 노드들
[1, 7], #4번 노드와 연결되어 있는 노드들
[2, 8], #5번 노드와 연결되어 있는 노드들
[2, 8], #6번 노드와 연결되어 있는 노드들
[4], #7번 노드와 연결되어 있는 노드들
[5, 6] #8번 노드와 연결되어 있는 노드들
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
bfs(graph, 1, visited)
탐색 순서: 1 -> 2 -> 3 -> 4 -> 5-> 6-> 7-> 8
👌 BFS를 사용하는 경우
1. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 2. 각 간선의 비용이 모두 동일한 상황에서 최단 거리를 해결하기 위한 목적으로 사용
