DFS와 BFS

📍 탐색 알고리즘: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- 그래프 탐색 알고리즘: DFS / BFS

 

---

DFS와 BFS 개념 다지기 전 배경 지식 ・・

 

 

📍 stack: 가장 나중에 들어온 데이터가 가장 먼저 출력됨 (LIFO)

- 스택 동작: 삽입 (append) / 삭제 (pop)

 

stack = [5, 2, 3, 1]

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

 

 

 

📍 queue: 가장 먼저 들어온 데이터가 가장 먼저 출력됨 (FIFO)

- 큐 동작: 삽입 (append) / 삭제 (popleft)

 

from collections import deque

queue = deque()

queue.append(5)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기 -> 나중에 들어온 순서대로 출력

 

 

 

📍 recursive : 자기 자신을 다시 호출하는 함수

 

def recursive_function():
    print('재귀 함수를 호출합니다')
    recursive_function()

recursive_function()

 

 

-  무한 재귀 함수

-  재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함 ! 

 

def recursive_function(i):
    if i == 100: # 종료 조건 
        return
    print('재귀 함수를 호출합니다')
    recursive_function(i+1) # 다음 함수를 부름

recursive_function(1)

 

 

 

💥 팩토리얼 구현 예제

 

# 반복적으로 구현한 팩토리얼
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)

 

 

 

 

💥 최대공약수 계산 (유클리드 호제법) 예제

- 유클리드 호제법:
1) 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 함

2) A와 B의 최대공약수는 B와 R의 최대공약수와 같음

 

ex) GCD(192, 162) = GCD(162, 30) = GCD(30, 12) = GCD(12, 6) = 6

 

def GCD(a, b):
    if a % b == 0:
        return b
    else:
        return GCD(b, a%b)
        
print(GCD(192, 162))

 

 

💥 재귀 함수 사용의 유의사항

- 재귀 함수를 사용하면, 복잡한 알고리즘을 더욱 간결하게 작성할 수 있음

- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음

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

= 스택을 사용해야 할 때, 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음

 

---

 

 

📍 DFS(Depth-First Search): 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘

- 일반적으로 stack 자료구조 혹은 재귀 함수를 이용한다. 

1) 탐색 시작 node를 stack에 삽입하고 방문 처리한다.

2) stack의 최상단 node에 방문하지 않은 인접한 node가 하나라도 있으면, 그 node를 stack에 넣고 방문 처리한다.

방문하지 않은 인접한 node가 없으면, stack에서 최상단 node를 꺼낸다.

3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

graph = [ # 각 노드가 연결된 정보를 표현 (2차원 리스트)
    [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]
]

visited = [False] * 9

def dfs(graph, v, visited):
    visited[v] = True # 현재 노드를 방문 처리
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

 

 

 

 

 

 

📍 BFS(Breadth-First Search): 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 일반적으로 queue 자료구조를 이용한다.

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.

2) 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접한 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

from collections import deque

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

visited = [False] * 9

def bfs(graph, start, visited):
    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

bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6