DFS/BFS

• 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.
  
  • 코딩 테스트에서 매우 자주 등장하는 유형

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
• 입구의 출구가 동일한 형태로 스택을 시각화 할 수 있다.
• 리스트 자료형을 사용
  • append()와 pop() 함수 사용

# append()와 pop()을 사용한다. => 상수시간 O(N)만큼 거림
stack = []

stack.append(5)
stack.append(2)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 입구와 출구가 모두 뚫려 있는 형태로 큐를 시각화 할 수 있다.
• deque 라이브러리를 사용
  • list로도 구현할 수 있으나, 시간복잡도가 더 높아 비효율적으로 동작할 수 있음
  • append()와 popleft() 함수 사용

from collections import deque

# 큐 구현을 위해 deque 라이브러리 사용=> 시간복잡도는 상수시간 O(N)
queue = deque()

queue.append(5)
queue.append(2)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 변환
print(queue) # 나중에 들어온 원소부터 출력

재귀 함수

def recursive_function(i):
	# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
    	return
    print(i, "번째 재귀함수에서", i + 1, "번째 재귀함수를 호출합니다.")
    recursive_function(i + 1)
    print(i, "번째 재귀함수를 종료합니다.")
    
recursive_function(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: # 1! or 0!은 1임
    	return 1
    # n! = n * (n-1)!를 그대로 코드로 작성
    return n * factorial_recursive(n - 1)
    
# 각각의 방식으로 구현한 팩토리얼 출력
print('반복적으로 구현: ', factorial_iterative(5))
print('재귀적으로 구현: ', factorial_recursive(5))

유클리드 호제법

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
• 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라 하자.
  이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있다.

def gcd(a, b):
	if a % b == 0:
    	return b
    else:
    	return gcd(b, a % b)

print(gcd(192, 162))

재귀 함수 사용의 유의 사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
  • 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
  • 반대로 모든 반복문은 재귀함수로 동일한 기능을 구현할 수 있다.
  • 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
  • 따라서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다. 

---

DFS (Depth-First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
  
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 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)