Graph Theory

이 글에서 알아볼 것은 그래프 이론입니다. 이산수학을 들은 분이라면 굉장히 익숙할 만한 주제입니다. 그래프 이론 자체가 특별한 알고리즘이 있는 것은 아니지만 앞으로 살펴볼 수많은 알고리즘과 자료구조 등 수많은 것들의 기반이 됩니다.

여기서 말하는 그래프는 그래프는 수학에서의 x축 y축이 있는 그래프와는 완전 다릅니다. 컴퓨터 과학에서의 그래프란 아래의 그림과 같은 형태를 의미합니다.

위 그림에서 번호가 쓰여 있는 동그라미를 노드(node) 또는 정점이라고 합니다. 지금은 이런 형태를 가지고 있지만, 격자, 지도, 수직선 등 사실상 모든 것을 그래프의 형태로 표현할 수 있습니다. 노드를 잇고 있는 선을 간선, 또는 vertex, edge라고 합니다. 그래프는 여러 node 들의 연결 상태를 나타내는데 효과적인 형태입니다. 사람들의 관계, 분자구조, 작업의 순서 등을 그래프로 나타낼 수 있습니다.

위 그림의 간선은 방향이 없습니다. 이런 간선으로 이루어진 그래프를 무방향(undirected) 그래프라고 합니다. 이런 그래프에서는 연결되어 있기만 하다면 원하는 방향으로 이동할 수 있습니다. 방향(directed) 그래프는 간선에 화살표를 이용해서 표현하고 그 방향대로만 이동할 수 있습니다.

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

위 그래프는 방향 그래프이면서 가중치가 있는 그래프의 예시입니다. 1번 노드에서 2번 노드로는 가중치 3의 간선이 존재하고, 3번 노드에서 4번 노드로는 가중치 2의 간선이 존재합니다.

그래프의 표현

그래프를 코드로 이해하려면 그래프의 연결 구조를 표현해야 합니다. 문제에서 그래프가 주어질 때는 노드의 개수 \( n \), 간선의 개수 \( m \)이 주어지고 그 다음 \( m \)개의 줄에 걸쳐서 간선의 정보가 주어집니다.

다음과 같이 입력이 주어진다고 가정하겠습니다. 첫 번째 줄에 노드의 개수 \( n \), 간선의 개수 \( m \)이 주어지고, 그 다음 \( m \)개의 줄에 걸쳐서 각 간선을 이루는 두 노드의 번호가 주어집니다. 노드는 1번부터 \( n \)번까지 번호가 매겨져 있습니다. 다음 \( m \)개의 줄에 걸쳐서 두 정수 \( u \), \( v \)가 주어집니다. 이는 \( u \)번 노드와 \( v \)번 노드가 양방향 간선으로 연결되어 있음을 의미합니다.

인접 행렬 (Adjacent Matrix)

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

int main() {
    int n, m; cin >> n >> m;

    bool adj[n + 1][n + 1];
    memset(adj, false, sizeof(adj));

    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u][v] = true;
        adj[v][u] = true;
    }
}

지금은 무방향 그래프이기 때문에 adj[u][v] 와 adj[v][u] 둘 다 1로 설정해 주었습니다. 그리고, 가중치가 없는 그래프이기 때문에 bool형 배열로 표현했습니다. 만약 가중치가 있는 그래프라면 int형 배열로 선언하고, 연결되어 있지 않은 수를 INF(1e9 등)으로 설정해 주면 됩니다.

인접 리스트 (Adjacent List)

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

int main() {
    int n, m; cin >> n >> m;
    vector<int> adj[n + 1];

    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

마치며

두 방법은 각각 다른 장단점이 있습니다. 본인이 사용하고자 하는 코드의 목적에 맞게 적절한 방법을 선택해서 사용해야 합니다. 앞으로 그래프 이론을 기반으로 한 여러 알고리즘을 다뤄볼 예정입니다. 그래프 이론은 최단경로, 트리, 네트워크 플로우 등 수많은 알고리즘의 기반이 됩니다. 지금 살펴본 내용 만으로는 아직 문제를 풀 수 없으니 이번 챕터의 연습문제는 없습니다.