자료구조: 그래프 (Graph)

그래프 (Graph) 자료구조 완벽 가이드

소프트웨어 엔지니어링 인터뷰에서 가장 어렵고 자주 출제되는 주제 중 하나인 **그래프(Graph)**에 대해 알아보겠습니다. 현실 세계의 복잡한 네트워크(소셜 네트워크, 지도, 라우팅 등)를 모델링하는 데 필수적인 자료구조입니다.

1. 그래프(Graph)란?

그래프는 **정점(Vertex, 또는 노드 Node)**과 이들을 연결하는 **간선(Edge)**으로 이루어진 비선형 자료구조입니다. 트리가 계층적 구조를 나타낸다면, 그래프는 객체들 간의 다대다(N:N) 관계를 표현합니다. 사실 트리는 사이클이 없는 특수한 형태의 그래프입니다.

• 정점 (Vertex/Node): 데이터를 저장하는 기본 단위입니다.
• 간선 (Edge): 정점 간의 연결 관계를 나타내는 선입니다.

2. 그래프의 종류

간선의 방향성과 가중치 유무에 따라 그래프를 분류할 수 있습니다.

• 무방향 그래프 (Undirected Graph): 간선에 방향이 없습니다. 정점 A와 B가 연결되어 있다면 A에서 B로, B에서 A로 모두 이동할 수 있습니다. (A, B) == (B, A)
• 방향 그래프 (Directed Graph / Digraph): 간선에 방향이 있습니다. 화살표로 표현되며, A에서 B로 가는 간선이 있다고 해서 B에서 A로 갈 수 있는 것은 아닙니다. (A, B) != (B, A)
• 가중치 그래프 (Weighted Graph): 간선에 비용(Cost)이나 가중치(Weight)가 할당된 그래프입니다. (예: 도시 간의 거리, 통신망의 대역폭 등)
• 사이클 / 비순환 그래프: 경로를 따라가다 보면 출발했던 정점으로 다시 돌아올 수 있는 경로를 ‘사이클(Cycle)‘이라고 합니다. 사이클이 없는 그래프를 비순환 그래프(Acyclic Graph)라고 하며, 방향성이 있으면서 사이클이 없는 그래프를 **DAG (Directed Acyclic Graph)**라고 부릅니다.

3. 그래프의 표현 방법

그래프를 컴퓨터 메모리에 저장하는 대표적인 방법 두 가지는 다음과 같습니다. 상황에 따라 유리한 방법이 다릅니다.

1) 인접 행렬 (Adjacency Matrix)

• 구조: $V\times V$ 크기의 2차원 배열(행렬)로 표현합니다. (V는 정점의 개수)
• 특징: 정점 $i$와 $j$가 연결되어 있으면 matrix[i][j] = 1 (또는 가중치), 연결되어 있지 않으면 0 (또는 무한대)으로 표기합니다.
• 장점: 두 정점 간의 연결 여부를 $O(1)$의 시간 복잡도로 매우 빠르게 확인할 수 있습니다.
• 단점: 정점의 개수가 많고 간선이 적은 희소 그래프(Sparse Graph)의 경우, 공간 복잡도가 $O(V^2)$이 되어 메모리 낭비가 심합니다.

2) 인접 리스트 (Adjacency List)

• 구조: 각 정점마다 연결된 정점들의 목록(리스트)을 저장합니다. (배열의 배열, 또는 리스트의 배열)
• 특징: 리스트, 연결 리스트 등을 사용하여 자신과 인접한 정점만 저장합니다.
• 장점: 필요한 메모리 공간만 사용하므로 공간 복잡도가 $O(V+E)$로 효율적입니다. (E는 간선의 개수) 특정 정점에 인접한 모든 정점을 순회할 때 빠릅니다.
• 단점: 두 정점 $u,v$가 연결되어 있는지 확인하려면 배열의 특정 인덱스의 리스트를 탐색해야 하므로 $O(V)$의 시간이 소요될 수 있습니다. (하지만 일반적으로 $V$보다 훨씬 적은 시간이 걸립니다.)

실무/인터뷰 팁: 대부분의 알고리즘 문제에서는 정점 대비 간선이 적은 희소 그래프가 주어지며, 인접 정점을 순회하는 연산이 빈번하므로 인접 리스트를 사용하는 것이 유리합니다. 파이썬에서는 딕셔너리(dict)나 리스트의 리스트(list of list)로 쉽게 구현할 수 있습니다.

4. 그래프 탐색 알고리즘

그래프의 모든 정점을 체계적으로 방문하는 방법은 크게 두 가지가 있습니다.

• DFS (깊이 우선 탐색, Depth-First Search): 갈 수 있는 한 깊게 파고들며 탐색하는 방법입니다. 스택(Stack)이나 재귀 함수를 사용하여 구현합니다. 경로의 특징(예: 사이클 검출, 백트래킹)을 알아야 할 때 유용합니다.
• BFS (너비 우선 탐색, Breadth-First Search): 현재 정점과 인접한 정점들을 먼저 모두 탐색한 후 다음 레벨로 넘어가는 방법입니다. 큐(Queue)를 사용하여 구현합니다. **최단 경로(Shortest Path)**를 찾을 때 주로 사용됩니다.

5. 그래프 주요 알고리즘 및 활용

1. 최단 경로 알고리즘: 다익스트라(Dijkstra, 가중치 그래프 최단경로), 벨만-포드(Bellman-Ford, 음수 가중치 허용), 플로이드-워셜(Floyd-Warshall, 모든 정점 간 최단경로)
2. 최소 신장 트리 (MST, Minimum Spanning Tree): 크루스칼(Kruskal), 프림(Prim) 알고리즘. 그래프의 모든 정점을 최소한의 비용으로 연결하는 트리 구조를 찾습니다.
3. 위상 정렬 (Topological Sort): 방향 비순환 그래프(DAG)에서 정점들의 선후 관계(순서)를 위배하지 않도록 나열하는 알고리즘입니다. (예: 대학 선수과목, 빌드 순서 결정 등)

요약

그래프는 객체 간의 관계를 표현하는 강력한 도구입니다. 인접 행렬과 인접 리스트의 차이점, 그리고 DFS와 BFS의 동작 원리와 차이를 명확히 이해하고 구현할 수 있어야 합니다. 다양한 알고리즘 문제의 근간이 되므로 철저한 학습이 필요합니다.