파이썬으로 배우는 그래프 탐색: DFS와 BFS 마스터하기
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 파이썬으로 구현하고, 실제 코딩 테스트에서 자주 만나는 문제 유형과 해결 전략까지 알아보는 심도있는 가이드입니다. 이 글에서는 단순한 개념 설명을 넘어, 여러분이 직접 코드를 작성하고 이해할 수 있도록 실제 예제와 함께 자세히 다루겠습니다. 그럼, 흥미진진한 그래프 탐색의 세계로 함께 떠나볼까요?
1. 그래프, 뭘까요? 인접 리스트로 그래프 표현하기
자, 그래프 탐색이라는 말부터 낯설게 느껴지시는 분들도 계실 거예요. 사실 그래프는 우리 주변에서 흔히 볼 수 있는 데이터 구조입니다. 예를 들어, 소셜 네트워크에서 친구 관계를 나타내거나, 지도에서 도시와 도로의 연결을 표현할 때 그래프를 사용할 수 있어요. 어때요? 생각보다 친숙하죠?
그래프는 여러 가지 방법으로 표현할 수 있지만, 파이썬에서는 인접 리스트(adjacency list)를 사용하는 것이 가장 효율적입니다. 인접 리스트는 각 노드(node)에 연결된 다른 노드들을 리스트로 저장하는 방식입니다. 만약 노드 A가 노드 B, C와 연결되어 있다면, 인접 리스트에서는 A를 키(key)로 하고 [B, C]를 값(value)으로 갖는 형태로 저장됩니다.
파이썬 딕셔너리를 이용하면 인접 리스트를 간편하게 구현할 수 있습니다. 예를 들어, 다음과 같은 그래프를 생각해볼게요.
1 -- 2
| |
| 3 -- 4그래프를 인접 리스트로 표현하면 다음과 같습니다.
graph = {
1: [2, 3],
2: [1],
3: [1, 4],
4: [3]
}? 키는 노드 번호이고, 값은 해당 노드와 연결된 노드들의 리스트입니다. 이렇게 간단하게 그래프를 표현할 수 있다니, 정말 매력적이죠? 이제 이 인접 리스트를 이용해서 DFS와 BFS를 구현해볼 텐데, 설레지 않으세요?
2. 깊이 우선 탐색(DFS): 깊숙이 파고드는 탐험
DFS는 말 그대로 깊이를 우선적으로 탐색하는 방법입니다. 하나의 경로를 따라 최대한 깊이 들어간 다음, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식이죠. 마치 미궁을 탐험하는 것과 같다고 생각하면 이해가 쉬울 거예요.
DFS는 주로 재귀 함수나 스택을 이용하여 구현됩니다. 재귀 함수는 코드가 간결하지만, 재귀 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다는 단점이 있어요. 반면, 스택을 이용한 반복적인 구현은 스택 오버플로우를 피할 수 있지만, 코드가 다소 복잡해질 수 있습니다. 어떤 방법을 선택할지는 여러분의 취향과 상황에 따라 결정하면 됩니다.
저는 개인적으로 재귀 함수가 더 직관적이라고 생각해요. 함수가 자기 자신을 호출하는 모습이 마치 깊숙한 곳으로 계속 내려가는 탐험가 같달까요? 다음은 재귀 함수를 이용한 DFS 구현 예제입니다.
def dfs_recursive(graph, node, visited):
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
visited = set()
dfs_recursive(graph, 1, visited) # 출력: 1 2 3 4 (순서는 구현에 따라 다를 수 있음), 이제 스택을 이용한 DFS를 살펴볼까요? 스택을 이용하면 재귀 호출 없이 DFS를 구현할 수 있습니다.
def dfs_iterative(graph, start_node):
visited = set()
stack = [start_node]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in reversed(graph.get(node, [])): # 중요! 방문 순서를 위해 역순으로 탐색
if neighbor not in visited:
stack.append(neighbor)
dfs_iterative(graph,1) # 출력: 1 3 4 2 (순서는 구현에 따라 다를 수 있음)? 재귀 함수와 스택을 이용한 DFS, 둘 다 매력적이지 않나요? 코드를 직접 실행해 보면서 어떤 방식이 더 이해하기 쉬운지 확인해 보세요.
3. 너비 우선 탐색(BFS): 가까운 곳부터 차근차근
BFS는 너비를 우선적으로 탐색하는 방법입니다. 마치 물결이 퍼져나가듯이, 시작 노드에서 가까운 노드부터 차례로 탐색해 나가는 방식이죠. BFS는 큐(queue) 자료구조를 사용하여 구현합니다. 큐의 FIFO(First-In-First-Out) 특성을 이용하여 가까운 노드부터 먼저 방문하게 됩니다.
BFS는 최단 경로를 찾는 알고리즘에서 자주 사용됩니다. 가중치가 없는 그래프에서 시작 노드로부터 다른 노드까지의 최단 경로를 찾는 데 효율적이에요. 예를 들어, 지도에서 두 도시 사이의 최단 경로를 찾을 때 BFS를 사용할 수 있습니다.
BFS는 큐를 사용하여 구현하는데, 코드는 다음과 같습니다.
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in sorted(graph.get(node, [])): # 중요! 방문 순서를 위해 정렬
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
bfs(graph, 1) # 출력: 1 2 3 4BFS는 DFS와 달리 큐를 사용하기 때문에 코드가 다소 다르지만, 기본적인 원리는 비슷합니다. 차근차근 코드를 따라가면서 BFS의 동작 방식을 이해해 보세요. 처음에는 어렵게 느껴질 수도 있지만, 한번 이해하고 나면 BFS의 효율성에 감탄하게 될 거예요!
4. DFS와 BFS, 어떤 알고리즘을 선택해야 할까요?
DFS와 BFS는 각각 장단점을 가지고 있습니다. 어떤 알고리즘을 선택할지는 문제의 특성과 목표에 따라 달라집니다.
| DFS | 구현이 간단하고, 메모리 사용량이 적다. | 최단 경로를 보장하지 않는다. | 모든 노드를 방문해야 하는 경우, 사이클 탐색 등 |
| BFS | 최단 경로를 보장한다. (가중치 없는 그래프) | 메모리 사용량이 DFS보다 많을 수 있다. | 최단 경로 탐색, 연결 요소 탐색 등 |
알고리즘 장점 단점 적합한 상황
표에서 보시다시피, DFS는 구현이 간단하고 메모리 효율이 좋지만, 최단 경로를 찾을 수 없다는 단점이 있습니다. 반면 BFS는 최단 경로를 찾을 수 있지만(가중치 없는 그래프에서), 메모리 사용량이 더 많을 수 있습니다. 따라서 문제 상황에 맞는 알고리즘을 선택하는 것이 중요합니다. 어떤 알고리즘이 더 적합한지 고민하는 과정 자체가 여러분의 알고리즘 설계 능력을 키우는 데 도움이 될 거예요. 이 부분은 여러 문제를 풀어보면서 감을 익히는 것이 중요합니다!
5. 자주 묻는 질문 (FAQ)
Q1: DFS와 BFS의 시간 복잡도는 어떻게 되나요?
A1: DFS와 BFS 모두 최악의 경우 O(V + E)의 시간 복잡도를 갖습니다. 여기서 V는 노드의 개수, E는 간선의 개수를 나타냅니다. 하지만 실제 실행 시간은 그래프의 구조와 시작 노드에 따라 달라질 수 있습니다.
Q2: DFS와 BFS 중 어떤 알고리즘이 더 효율적인가요?
A2: DFS와 BFS 중 어느 알고리즘이 더 효율적인지는 문제 상황에 따라 다릅니다. 만약 모든 노드를 방문해야 하고 최단 경로가 중요하지 않다면 DFS를 사용하는 것이 효율적입니다. 반대로 최단 경로를 찾아야 하는 경우에는 BFS를 사용하는 것이 더 효율적입니다.
Q3: 인접 행렬을 사용하는 방법은 없나요?
A3: 인접 행렬을 이용해서도 DFS와 BFS를 구현할 수 있습니다. 인접 행렬은 노드의 개수만큼의 크기를 가진 2차원 배열을 사용하여, 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표현합니다. 하지만 인접 리스트에 비해 메모리 효율이 떨어지기 때문에, 대부분의 경우 인접 리스트를 사용하는 것이 좋습니다. 특히, 노드의 수가 많고 간선의 수가 적은 희소 그래프에서는 인접 리스트가 훨씬 효율적입니다.
마무리
이번 포스팅에서는 DFS와 BFS 알고리즘에 대해 자세히 알아보고, 파이썬 코드를 통해 직접 구현해 보았습니다. DFS와 BFS는 그래프 탐색의 기본적인 알고리즘이며, 코딩 테스트에서 자주 출제되는 중요한 주제입니다. 이 포스팅이 여러분의 코딩 실력 향상에 도움이 되기를 바랍니다. 다음 포스팅에서는 더욱 다양하고 심화된 알고리즘들을 다뤄보도록 하겠습니다! 궁금한 점이나 추가적으로 다루었으면 하는 주제가 있다면 언제든지 댓글 남겨주세요! 감사합니다!
키워드: 파이썬, Python, DFS, 깊이우선탐색, BFS, 너비우선탐색, 그래프, Graph, 알고리즘, Algorithm, 코딩테스트, CodingTest, 자료구조, DataStructure, 인접리스트, AdjacencyList, 최단경로, ShortestPath, 재귀함수, RecursiveFunction, 스택, Stack, 큐, Queue, 프로그래밍, Programming, 개발, Development, 코딩, Coding, IT, 데이터과학, DataScience, 컴퓨터과학, ComputerScience, 파이썬알고리즘, PythonAlgorithm, 알고리즘공부, AlgorithmStudy, 코딩공부, CodingStudy, 이코테, 이것이취업을위한코딩테스트다
