Graph Theory

이 글에서 알아볼 것은 그래프 이론입니다. 이산수학을 들은 분이라면 굉장히 익숙할 만한 주제입니다. 그래프 이론 자체가 특별한 알고리즘이 있는 것은 아니지만 앞으로 살펴볼 수많은 알고리즘과 자료구조 등 수많은 것들의 기반이 됩니다. 컴퓨터 과학에서의 그래프는 수학에서의 x축 y축이 있는 그래프와는 완전 다릅니다. 컴퓨터 과학에서의 그래프란 아래의 그림과 같은 형태를 의미합니다.

위 그림에서 번호가 쓰여 있는 동그라미를 노드(node) 또는 정점이라고 합니다. 지금은 이런 형태를 가지고 있지만, 격자, 지도, 수직선 등 사실상 모든 것을 그래프의 형태로 표현할 수 있습니다. 노드를 잇고 있는 검은 선을 간선, 또는 vertex, edge라고 합니다. 그래프는 여러 node 들의 연결 상태를 나타내는데 효과적인 형태입니다. 사람들의 관계, 분자구조, 작업의 순서 등 굉장히 중요한 역할을 합니다. 위 그림의 간선은 방향이 없습니다. 이런 간선으로 이루어진 그래프를 무방향(undirected) 그래프라고 합니다. 이런 그래프에서는 연결되어 있기만 하다면 원하는 방향으로 이동할 수 있습니다. 방향(directed) 그래프는 간선에 화살표를 이용해서 표현하고 그 방향대로만 이동할 수 있습니다.

간선은 가중치를 가지기도 합니다. 가중치(weight)는 간선의 길이와 비슷한 개념입니다. 예를 들어, 지도를 그래프로 표현한다면, 먼 지역을 연결하는 도로는 큰 가중치를 갖게 됩니다. 가중치가 없는(unweighted) 그래프는 연결 정보만을 표현합니다.

그래프의 표현

그래프를 코드로 이해하려면 그래프의 연결 구조를 표현해야 합니다. 코드로 그래프를 표현하는 방식에는 크게 두가지 방법이 있습니다.

인접 행렬 (Adjacent Matrix)

\( n \)개의 노드가 있을 때 \( n \times n \)크기의 배열을 만들어서 연결관계를 표현하는 방식입니다. 예를 들어, 2번과 4번이 연결되어 있음을 표현하고 싶다면 adj[2][4] 를 true로 설정합니다. 이 방식은 간선의 개수가 적어도 항상 \( n^2 \)개의 데이터를 관리해야 합니다. 대신, 특정 두 노드의 연결 관계를 \( O(1) \)에 바로 알 수 있습니다. 하지만, 어떤 노드와 연결된 다른 노드의 리스트를 알고 싶다면 하나하나 탐색해야 합니다. 즉, \( O(n) \)의 시간복잡도를 갖게 됩니다.

인접 리스트 (Adjacent List)

\( n \)개의 데이터가 있을 때 \( n \)개의 배열(vector, list)를 담는 배열을 만들어서 관리하는 방식입니다. 예를 들어, 2번 노드와 4, 5, 6번 노드가 연결되어 있다면 adj[2] 는 [4, 5, 6] 이 됩니다. 이 방식은 연결되어 있는 노드의 정보만 포함하기 때문에 메모리를 적게 사용합니다. 그리고 특정 노드와 연결된 노드를 찾고 싶으면 adj[n] 으로 바로 찾을 수 있습니다. 대신, 특정 두 원소가 연결되어 있는지 확인하려면 배열을 하나하나 뒤져보며 찾아야 합니다.

두 방법은 각각 다른 장단점이 있습니다. 본인이 사용하고자 하는 코드의 목적에 맞게 적절한 방법을 선택해서 사용해야 합니다. 그래프 이론 자체로 알고리즘이 되진 않지만 앞으로 그래프에서 사용할 수 있는 알고리즘과 특수한 형태의 그래프를 알아볼 예정입니다. 그래프 이론은 저난이도부터 고난이도까지 다양한 알고리즘과 자료구조에서 사용되고 코딩테스트, 실무에서도 정말 다양하게 활용되는 내용인 만큼 확실히 알고 넘어가면 좋겠습니다.