안녕하세요, 여러분! 오늘은 컴퓨터 과학에서 가장 유용하고 흥미로운 자료구조 중 하나인 '그래프'에 대해 알아보려고 합니다.
그래프란 무엇인가?
흔히 '그래프'라고 하면 막대그래프, 원그래프, 선 그래프처럼 데이터를 시각화하는 차트를 떠올리실 수 있습니다. 하지만 컴퓨터 과학에서 말하는 그래프는 이와는 완전히 다른 개념입니다.
컴퓨터 과학에서의 그래프는 '노드(Node)'라고 불리는 정점들과 이들을 연결하는 '엣지(Edge)'라고 불리는 간선들로 구성된 자료구조입니다. 간단히 말해, 여러 개체(노드)와 이들 사이의 관계(엣지)를 표현하는 방법입니다.
그래프 관련 주요 용어
- 노드(Node) 또는 정점(Vertex): 그래프의 기본 요소로, 개체나 위치를 나타냅니다. 예를 들어 소셜 네트워크에서는 사용자가 노드가 됩니다.
- 엣지(Edge) 또는 간선: 두 노드 간의 연결을 나타냅니다. 소셜 네트워크에서는 친구 관계가 엣지에 해당합니다.
- 방향 그래프(Directed Graph): 엣지에 방향이 있는 그래프입니다. A→B 연결은 B→A 연결과 다릅니다. 예: 트위터에서의 팔로우 관계
- 무방향 그래프(Undirected Graph): 엣지에 방향이 없는 그래프입니다. A-B 연결은 B-A 연결과 동일합니다. 예: 페이스북에서의 친구 관계
- 가중치 그래프(Weighted Graph): 엣지에 가중치(비용 또는 거리 등)가 할당된 그래프입니다. 예: 도시 간 거리를 나타내는 지도
- 경로(Path): 한 노드에서 다른 노드로 가는 엣지들의 시퀀스입니다.
- 사이클(Cycle): 시작 노드로 돌아오는 경로입니다.
그래프는 실생활의 다양한 관계와 네트워크를 표현하는 데 매우 유용합니다. 소셜 미디어의 인간관계, 도로 네트워크, 컴퓨터 네트워크, 웹 페이지 간의 링크 등 우리 주변의 많은 것들이 그래프로 모델링 될 수 있습니다.
그래프를 구현하는 두 가지 방법
그래프는 노드(정점)와 에지(간선)로 구성된 자료구조로, 다양한 관계를 표현하는 데 활용됩니다. 그래프를 구현하는 방법에는 크게 두 가지가 있습니다: 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다.
인접 행렬(Adjacency Matrix)
인접 행렬은 2차원 배열을 사용하여 그래프를 표현합니다. 행과 열은 그래프의 노드를 나타내며, 배열의 값은 두 노드 간의 연결 여부를 나타냅니다.
장점:
- 구현이 간단하고 직관적입니다.
- 두 노드 간의 연결 여부를 O(1) 시간에 확인할 수 있습니다.
- 가중치 그래프 구현이 용이합니다.
단점:
- 노드 수가 많을 경우 메모리 사용량이 O(V²)로 증가합니다.
- 희소 그래프(간선이 적은 그래프)에서는 공간 낭비가 심합니다.
- 모든 간선을 순회하려면 O(V²) 시간이 필요합니다.
인접 리스트(Adjacency List)
인접 리스트는 각 노드마다 연결된 노드들의 리스트를 유지하는 방식입니다. 보통 배열이나 해시 테이블과 연결 리스트의 조합으로 구현합니다.
장점:
- 메모리 사용량이 O(V+E)로, 희소 그래프에서 효율적입니다.
- 특정 노드와 연결된 모든 노드를 쉽게 순회할 수 있습니다.
- 새로운 노드 추가가 용이합니다.
단점:
- 두 노드 간의 연결 여부를 확인하는 데 O(V) 시간이 필요할 수 있습니다.
- 구현이 인접 행렬보다 복잡합니다.
- 무작위 접근이 어렵습니다.
선택 기준은 그래프의 특성과 수행할 작업에 따라 달라집니다. 희소 그래프나 동적으로 변하는 그래프는 인접 리스트가 유리하고, 밀집 그래프나 간선 조회가 빈번한 경우에는 인접 행렬이 적합합니다.
그래프 순회와 기본 알고리즘
그래프를 코드로 구현해서 무엇을 할 수 있는지를 알아야겠죠. 그래프의 모든 정점을 방문하는 순회 방법과 그래프에서 자주 사용되는 알고리즘들은 다양한 문제 해결의 기반이 됩니다. 이 알고리즘들을 이해하고 적용하는 능력은 그래프 문제를 푸는 데 필수적입니다.
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 구현
DFS는 현재 정점에서 가능한 깊이 들어가며 탐색하는 방식입니다. 스택 또는 재귀를 사용하여 구현합니다. 미로 탐색, 연결 요소 찾기, 위상 정렬 등에 활용됩니다.
BFS는 현재 정점과 가까운 정점부터 탐색하는 방식입니다. 큐를 사용하여 구현하며, 최단 경로 문제, 네트워크 분석 등에 활용됩니다. 두 방식 모두 인접 리스트에서는 O(V+E), 인접 행렬에서는 O(V²)의 시간 복잡도를 가집니다.
구체적인 구현은 다음 포스팅에서 알아보겠습니다.
최단 경로 알고리즘 (다익스트라)
다익스트라 알고리즘은 음이 아닌 가중치 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 우선순위 큐를 사용하여 효율적으로 구현할 수 있으며, 내비게이션 시스템이나 네트워크 라우팅에 널리 사용됩니다. 조금 난이도 있는 코딩테스트에서 자주 나옵니다.
사이클 탐지 알고리즘
그래프 내에 사이클이 존재하는지 확인하는 알고리즘은 DFS를 활용합니다. 방향 그래프와 무방향 그래프에서의 구현 방식이 약간 다르며, 작업 스케줄링, 의존성 분석 등 다양한 응용 분야에서 중요합니다.
인접 행렬은 그래프를 구현하는 가장 기본적인 방법 중 하나입니다. 이외에도 인접 리스트, 엣지 리스트 등 다양한 구현 방법이 있으며, 각각 특정 상황에서의 장단점이 있습니다. 아래는 인접 행렬을 이용한 문제와 구현입니다. 다음 포스팅에서는 인접 리스트를 이용한 구현 방법과 인접 행렬과 인접 리스트의 차이에 대해 더 자세히 알아보겠습니다.