[이것이 코딩 테스트다] DFS / BFS

 

 

1. 자료구조 기초

- 그래프 탐색 알고리즘

: 탐색 = 많은 양의 데이터 중 원하는 데이터 찾는 과정

: 대표 그래프 탐색 알고리즘 ) DFS, BFS

 

 

- 스택 자료구조 (Stack)

: 선입후출(LIFO)의 자료구조

: 입구와 출구가 동일

: 삽입 / 삭제 로 동작

: 리스트를 사용하여 구현 (삽입 : append / 삭제 : pop / 최상단 원소부터 출력: [ : : 1])

: 대표 예 ) 박스 쌓기

 

 

- 큐 자료구조 (Queue)

: 선입선출(FIFO)의 자료구조

: 입그와 출구가 모두 뚫려있는 형태

: 삽입 / 삭제 로 동작

: 오른쪽 → 왼쪽  방향

: deque 라이브러리(큐)를 사용하여 구현 (from collections import deque / queue = deque() / 삽입: append / 삭제: popleft())

: 리스트로도 구현할 수 있지만, 시간 복잡도가 높아서 비효율적으로 동작할 수 있음

: 대표 예 ) 대기열

 

 

- 재귀함수 (Recursive Function)

: 재귀함수 = 자기 자신을 다시 호출하는 함수

: 재귀함수 예제

def recursive_function():
	print('재귀함수를 호출')
    	recursive_function()
    
recursive_function();

  문자열 무한 출력 → 어느정도 출력하다가 최대 재귀 깊이 초과 시 오류 메시지 출력 (무한으로 재귀 호출 진행 X)

 

 

- 재귀함수의 종료 조건

: 재귀 함수의 종료 조건을 반드시 명시해야 함

: 종료 조건을 제대로 명시하지 않으면 → 함수가 무한히 호출

 

1) 예제 - 팩토리얼 구현

: n! = 1 x 2 x 3 x ... x (n-1) x n

: 0! = 1, / 1! = 1

# for문을 사용한 n!
def factorial_iterative(n):
    result = 1    
    for i in range(1, n+1): # 1~n까지 곱하기
    	result *= i
    return result
    
# 재귀함수를 사용한 n!
def factorial_recursive(n):
    if n <= 1: # 0, 1 팩토리얼은 1
        return 1
    return n * factorial_recursive(n-1) # n! = n * (n-1)!
    
print(factorial_iterative(5)) # 120
print(factorial_recursive(5)) # 120

: 반복문으로 구한 것 보다, 재귀함수를 사용한 코드가 더 간결하고 직관적!

 

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

: 두 자연수 A, B에 대해서  →  (A>B 일 때) A%B == R 

: gcd(A,B) == gcd(B,R)

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

print(gcd(192, 162)) # 6

 

 

- 재귀함수 사용 시 유의사항

: 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있기 때문에 신중히 사용해야 함

: 모든 재귀함수는 반복문을 이용해서 동일한 기능을 구현할 수 있음

: 재귀함수가 항상 반복문보다 유리하지는 않음 (유리할수도, 불리할수도)

: 컴퓨터가 함수를 연속으로 호출 → 컴퓨터 메모리 내부 스택 프레임에 쌓임

: 때문에 스택 사용 시 → 스택 라이브러리 대신에 재귀함수 이용하는 경우가 많음

 

 

 

2. DFS (Depth-First Search)

- DFS 개념

: DFS (깊이 우선 탐색) = 그래프에서 깊은 부분 우선적으로 탐색하는 알고리즘

: 스택 (또는 재귀함수) 사용

1. 시작 노드 → 스택에 삽입 → 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 → 스텍에 삽입 → 방문처리
   (방문하지 않은 노드 X → 스택에서 최상단 노드 꺼냄)
3. 반복

방문기준 : 번호가 낮은 인접 노드 부터

‣ 탐색 순서 : 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

def dfs(graph, v, visited):
    visited[v] = True  # 방문 처리
    print(v, end='')
    
    for i in graph[v]:  # 재귀적으로 방문
        if not visited[i]:
            dfs(graph, i, visited)

# 노드들이 연결된 정보
graph = [
    [],  # 0번째 처리
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False]*9  # 방문 정보

dfs(graph, 1, visited)

 

 

 

3. BFS (Breadth-First Search)

- BFS 개념

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

: 큐 사용

1. 시작 노드 → 큐에 삽입 → 방문처리
2. 큐에서 노드 꺼냄 → 인접 노드 중에서 방문하지 않은 노드들 모두 큐에 삽입 → 방문처리
3. 반복

방문기준 : 번호가 낮은 인접 노드 부터

‣ 탐색 순서 : 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])  # deque 라이브러리 사용
    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

# 노드들이 연결된 정보
graph = [
    [], 
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False]*9  # 방문 정보

bfs(graph, 1, visited)