그래프

그래프란 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미합니다. 주어진 문제에서 ‘서로 다른 개체(혹은 객체)가 연결되어 있다’라고 언급되어 있다면 그래프 알고리즘으로 해결해야 할 확률이 높습니다.

그래프 자료구조 중에 트리 자료구조가 있습니다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델입니다. 최소 힙이나 최대 힙이 트리 자료구조에 속합니다. 최소 힙은 부모의 값이 자식의 값보다 항상 작은 자료구조입니다.

그래프를 구현하는 방법은 2가지가 있습니다.

1. 인접 리스트: 리스트를 사용하는 방식
2. 인접 행렬: 2차원 배열을 사용하는 방식

노드의 개수가 V, 간선의 개수가 E인 그래프가 있다고 생각해봅시다. 인접 리스트를 사용할 때는 O(E)만큼의 메모리 공간이 필요합니다. 인접 행렬을 저장하기 위해서 O(V^2)만큼의 메모리 공간이 필요합니다. 인접 행렬은 특정한 노드 A에서 특정한 노드 B로 이어진 간선의 비용을 알아낼 때 O(1)만큼의 시간이 소요되는 장점이 있습니다. 반면 인접 리스트는 O(V)만큼의 시간이 소요됩니다.

인접 리스트를 코드로 구현하면 다음과 같습니다.

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

인접 행렬을 코드로 구현하면 다음과 같습니다.

INF = 999999999  # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

print(graph)

코딩 테스트에 자주 출제되는 다양한 그래프 알고리즘이 있습니다.

1. 탐색 알고리즘: DFS, BFS
2. 최단 경로 알고리즘: 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘