이것이 코테다 영상 강의 - DFS, BFS

탐색(search) : 많은 양의 데이터중에서 원하는 데이터를 찾는 과정
-> 대표 유형 : DFS, BFS

필요한 자료구조

• 스택(stack)
• 큐(queue)

#스택 구현 예제
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])
print(stack)

#큐 구현 예제
from collections import 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()

print(queue)
queue.reverse()
print(queue)

재귀 함수 (recursive funtion) : 자기 자신을 다시 호출하는 함수

• 파이썬은 재귀 깊이 제한이 있다. (따로 설정해야 함)
• 종료조건을 꼭 명시 해야한다.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능 구현 가능

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

• 스택 사용시 위 이류 때문에 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

#재귀 함수 구현 예제
def recursive_function():
    print('im recursive')
    recursive_function()

recursive_function()

#팩토리얼 구현 
#반복적으로 구현
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

#재귀적으로 구현
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

print(factorial_iterative())
print(factorial_recursive())

DFS (Depth-First Search)

• 깊이 우선 탐색이라고 하며, 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료 구조(혹은 재귀 함수)를 이용
• 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번 과정 종료 때까지 반복

#BFS 구현 예제
from collections import deque

def bfs(graph, start, visited):
    #큐 구현
    queue = deque([start])
    #현재 노드 방문 처리
    visited[start] = True
    #큐가 빌 때 까지(false) 반복
    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)