[자료구조] 그래프 기초 (DFS, BFS)

들어가며

그래프란 무엇인가? 우리 어렸을때 놀던 놀이터를 생각하면 편하다. 우리가 흔히 노는 놀이터는 여러 놀이기구가 있다. 그네도 있고 미끄럼틀도 있고 여러 놀이기구가 있는데 어떤 놀이기구는 서로 연결되어 있어서 한 놀이기구에서 다른 놀이기구로 걸어갈수 있다. 그래프는 이렇게 서로 연결된 것들을 표현 하는 도구이다.

정점(Vertex): 놀이기구와 같다. 그래프에서는 각각의 장소나 사물을 나타낸다. 간선(Edge): 두 놀이기구 사이의 길과 같다. 그래프에서는 두 정점이 어떻게 연결되어 있는지를 나타낸다.

DFS (Depth First Search, 깊이 우선 탐색)

놀이터에서 놀이기구를 타기로 했다. 하지만 어떤 놀이기구부터 탈지 결정하기 어려울수 있다. 그래서 우리는 가장 가까운 놀이기구부터 타기로 결정 했다. 그 놀이기구를 탄 후에는 그 놀이기구와 연결된 다른 놀이기구로 걸어가서 타게 된다. 이런 식으로 계속해서 탈 수 있는 놀이기구가 없을 때까지 놀이기구를 된다.

DFS는 이런 방식으로 동작한다. 시작 정점에서 시작해서 방문하지 않은 인접한 정점을 하나씩 깊게 탐색하는 방법이다.

BFS (Breadth First Search, 너비 우선 탐색)

이번에는 다르게 놀이기구를 타본다고 가정 한다. 이번에는 우리가 있는 위치에서 가장 가까운 모든 놀이기구를 먼저 타고, 그 다음으로 먼 것들을 타기로 결정했다.

BFS는 이런 방식으로 한다. 시작 정점에서 시작해서 방문하지 않은 모든 인접한 정점을 너비 방향으로 탐색하는 방법이다. 큐(Queue)라는 도구를 사용해서 탐색을 진행하곤 한다.

그래프 표현하기

우리는 먼저 그래프를 어떻게 파이썬 코드로 표현할지 알아봐야 한다. 일반적으로 인접 리스트(Adjacency List) 방식을 사용한다.

# 그래프 예제
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

이 코드는 놀이기구들이 어떻게 서로 연결되어 있는지 나타낸다. 예를 들어, A 놀이기구는 B와 C 놀이기구와 연결되어 있다는 것을 알 수 있다.

DFS (깊이 우선 탐색)

DFS는 재귀를 사용하거나 스택을 사용해서 구현할 수 있다. 여기서는 스택을 사용한 예제를 작성해 보려고 한다.

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    
    return visited

1. visited는 우리가 이미 방문한 놀이기구를 기억하기 위한 집합이다.
2. stack은 다음에 방문할 놀이기구들을 저장하는 데 사용된다. 시작 놀이기구는 start이다.
3. while stack: 반복문은 stack에 놀이기구가 남아있는 동안 계속 실행된다.
4. vertex = stack.pop()에서 가장 마지막에 추가된 놀이기구를 가져온다.
5. 만약 해당 놀이기구를 아직 방문하지 않았다면, 방문 목록에 추가하고, 그 놀이기구와 연결된 다른 놀이기구들을 stack에 추가한다.

BFS (너비 우선 탐색)

BFS는 큐를 사용하여 구현한다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)

    return visited

1. visited는 여전히 우리가 이미 방문한 놀이기구를 기억하기 위한 집합이다.
2. queue는 다음에 방문할 놀이기구들을 저장하는 데 사용된다. 시작 놀이기구는 start이다.
3. while queue: 반복문은 queue에 놀이기구가 남아있는 동안 계속 실행된다.
4. verte = queue.popleft()에서 가장 먼저 추가된 놀이기구를 가져온다.
5. 만약 해당 놀이기구를 아직 방문하지 않았다면, 방문 목록에 추가하고, 그 놀이기구와 연결된 다른 놀이기구들을 queue에 추가한다.

그래프와 함께 함수 테스트하기

print(dfs(graph, 'A'))  # {'A', 'B', 'C', 'D', 'E', 'F'}
print(bfs(graph, 'A'))  # {'A', 'B', 'C', 'D', 'E', 'F'}

요약

1. 그래프는 서로 연결된 정점과 간선으로 이루어진 도구이다.
2. DFS는 깊게 탐색하면서 더 이상 갈 곳이 없을 때까지 방문하는 방법이다.
3. BFS는 넓게 탐색하면서 가장 가까운 곳부터 방문하는 방법이다.

결론

그래프는 다양한 상황에서 서로 연결된 정보를 나타내는 데 사용되는 중요한 자료 구조이다. 복잡한 네트워크나 시스템을 간단한 형태로 나타낼 수 있기 때문에, 그래프를 이해하는 것은 컴퓨터 과학과 실제 세계 문제 해결에서 근본적인 중요성을 지니고 있다.

우리가 살펴본 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)는 그래프를 탐색하는 가장 기본적인 알고리즘이다. 이 두 알고리즘은 각각 서로 다른 방식으로 그래프의 모든 정점을 방문하며, 어떤 문제 상황에 더 적합한지는 문제의 특성과 요구사항에 따라 달라진다.

DFS는 깊게, BFS는 넓게 탐색하는 특징을 가지며, 이 두 알고리즘은 그래프의 구조와 특성을 분석하거나 그래프 상의 경로를 찾는 데 주로 활용된다. 또한, 이 알고리즘들은 다양한 응용 분야에서 기반으로 사용되어, 더 복잡한 알고리즘의 원리를 이해하는 데도 중요한 역할을 한다.

프로그래밍을 통해 이러한 알고리즘을 구현하고 이해하면, 실제 세계의 복잡한 문제들을 코드로 풀어나가는 능력을 키울 수 있다. 그래프와 그래프 탐색 알고리즘은 앞으로의 문제 해결 능력을 다음 단계로 끌어올릴 수 있는 핵심 도구이다.

맨 위로 올라가기