[22.08.13] DFS BFS
나동빈 알고리즘 강의_ DFS, BFS
#dfs #bfs
-
그래프 탐색 알고리즘 : DFS/ BFS
- 탐색이란 많은 데이터 중에서 원하는 데이터를 찾는 과정
- DFS/ BFS는 코테에서 매우 중요
-
스택 자료구조
- 선입후출
- 입구와 출구가 동일한 형태
- 박스 쌓기로 생각
-
큐 자료구조
- 선입선출
- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
- 줄서기로 생각
- 파이썬은 리스트로 사용하면 시간 복잡도가 올라가므로 무조건 deque사용!
-
재귀함수
-
자기 자신을 다시 호출하는 함수 (Recursive Function)
def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function()- 파이썬에서는 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지 만날 수 있다.
- 제한을 느슨하게 하는 방법도 존재한다. 하지만 보통 코딩테스트에서는 제한 안에서 작동되도록 한다.
-
재귀 함수의 종료 조건
- 재귀 함수 문제 풀이에서 재귀 함수의 종료 조건은 반드시 명시해야 한다.
- 종료 조건이 없으면 함수가 무한히 호출될 수 있다.
def recursive_function(i): # 100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, '번째 재귀함수에서',i+1, '번째 재귀함수를 호출합니다.') recursive_function(i+1) print(i, '번째 재귀함수를 종료합니다.') recursive_function(1) -
팩토리얼 구현 예제
- n! = 1 x 2 x 3 x … x n
- 수학적으로 0! 과 1! 의 값은 1입니다.
# 반복적으로 구현한 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)) -
최대공약수 계산 (유클리드 호제법) 예제
-
두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
-
유클리드 호제법이란
두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
-
유클리드 호제법 아이디어 그대로 재귀 함수 작성
-
예시 : GCD(192, 162)
단계 A B 1 192 162 2 162 30 3 30 12 4 12 6 def gcd(a, b): if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162))
-
-
-
재귀 함수 사용의 유의 사항
- 복잡한 알고리즘 간결하게 장성 가능 but 다른 사람이 이해하기 어려워 질 수 있다.
- 반복문을 통해 동일한 기능 구현 가능
- 반복문 보다 재귀함수가 유리한 경우, 불리한 경우 모두 존재
- 함수를 연속적으로 호출하면 메모리 내부에 스택 프레임 쌓인다. 스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 사용하기도 한다.
-
-
DFS(Depth-First Search)
-
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
-
스택 자료구조 이용 ( 혹은 재귀 함수 )
- 탐색 시작 노드를 스택에 삽입, 방문처리
- 인접 노드에서 방문하지 않은 노드는 스택에 쌓음
- 방문한 노드만 존재하면 스택에서 꺼낸다
- 위의 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)
-
너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘
-
큐 자료구조 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입, 방문처리
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
-
BFS 소스코드 예제
from collections import deque # BFS 메서드 정의 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, 7], [1, 4, 5], [3, 5], [3, 4] [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 ( 1차원 리스트 ) visited = [False] * 9 # 정의된 BFS 함수 호출 bfs(graph, 1, visited)
-