코딩테스트를 대비한 알고리즘 포스팅 해시(Hash)편은 여기 참고 !
코딩테스트를 대비한 알고리즘 포스팅 스택/큐(Stack/Queue)편은 여기 참고 !
코딩테스트를 대비한 알고리즘 포스팅 힙(Heap)편은 여기 참고 !
코딩테스트를 대비한 알고리즘 포스팅 정렬(Sort)편은 여기 참고 !

---

🐣 그래프 탐색(DFS/BFS)이란 ?

네번째로 정리할 알고리즘인 그래프 탐색 알고리즘: DFS/BFS 은 많은 양의 데이터 중에서 원하는 데이터를 찾는 문제이다. 즉, 그래프의 형식을 활용해 많은 양의 데이터에서 빠르게 데이터를 찾는 것.

그래프 탐색 알고리즘인 DFS와 BFS를 학습하기 위해선 스택, 큐, 재귀함수의 자료구조를 먼저 이해하는 것이 필요하다.

---

재귀함수

앞서 언급한 자료구조 중 스택과 큐는 여기에 정리하였으므로, 재귀함수를 예시를 들어 정리하도록 하겠다 !

재귀함수(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: # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n * (n-1)!
    return n * factorial_recursive(n-1)

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 내부의 스택 프레임에 쌓이게 되는데, 스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 이용하는 경우도 많다.

---

DFS(Depth First Search)

DFS는 깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS는 스택 자료구조(or 재귀함수)를 이용하며 동작 과정은 아래와 같다.

스택은 후입선출(LIFO) 구조

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복한다.

그래프 예시를 통한 설명

파이썬으로 구현한 DFS

# 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번 노드와 연결
    [1,7], # 2번 노드와 연결
    [1,4,5], # ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

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

---

BFS

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

BFS는 큐 자료구조를 이용하며 동작과정은 아래와 같다.

큐는 선입선출(FIFO) 구조

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

그래프 예시를 통한 설명

파이썬으로 구현한 BFS

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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

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

---

해당 알고리즘을 활용하면 좋은 문제

• 각 간선의 비용이 모두 동일한 상황에서 최단 거리, 임의의 경로를 찾는 문제(BFS)
• 그래프에서 모든 노드를 전부 방문하고자 하는 문제(DFS/BFS 둘다 가능하지만 DFS가 더 간단)

---

해당 포스팅을 작성하는데 참고한 블로그

• 알고리즘 깊이우선탐색DFS과 너비우선탐색BFS
• 깊이우선탐색DFS과 너비우선탐색BFS

DFS/BFS 알고리즘을 활용한 코딩테스트 문제 풀이