본문 바로가기

코딩/알고리즘

[초급] 그래프

이번 게시글에서는 그래프가 무엇인지에 대해서 살펴보겠습니다.

그래프

그래프는 정점들이 간선들로 연결되어 있는 형태를 말합니다. 여기서 정점은 교차로와 비슷한 개념이고, 간선은 도로와 비슷한 개념입니다.

 

왼쪽과 같은 그래프에서 정점은 총 6개이고, 간선은 총 8개입니다. 오른쪽 그래프에서 정점은 총 8개이고, 간선은 5개입니다.

 

간선에 방향이 있는 그래프를 유방향 그래프, 방향이 없는 그래프를 무방향 그래프라고 합니다. 위에 있는 그래프는 모두 무방향 그래프입니다.

 

아무 두 정점이나 잡았을 때, 간선을 통해 오고 갈 수 있다면 연결 그래프(connected graph)라고 합니다. 연결 그래프가 아닌 그래프(disconnected graph)에서, 간선을 통해 서로 오고 갈 수 있는 점들의 집합을 연결 성분(connected component)이라고 합니다. 모든 연결 그래프에서, 연결 그래프는 그 자체로 연결 성분이며, 연결 성분의 개수는 1개입니다. 왼쪽 그래프는 연결 그래프이며, 오른쪽 그래프는 연결 그래프가 아닙니다. 오른쪽 그래프에서 연결 성분은 [0, 1, 2], [3, 4, 5, 7], [6]의 3개입니다.

 

같은 간선을 두 번 거치지 않고 원래 정점으로 돌아오는 경로를 회로(cycle)라고 합니다. 회로가 있는 그래프를 순환 그래프(cyclic graph), 없는 그래프를 비순환 그래프(acyclic graph)라고 합니다. 위 두 그래프에는 모두 회로가 없습니다.

 

각 간선에 가중치가 있는 그래프도 있는데, 이러한 그래프를 가중치 그래프라고 합니다. 이때 가중치의 예로는 거리, 시간, 통행료, 용량 등이 있습니다. [각주:1]

 

그래프의 저장

그래프를 프로그래밍 언어에서 어떻게 다루는지 알아봅시다.

 

가장 중요한 것은 정점과 간선의 개수입니다. 보통 정점의 개수는 $n$, 간선의 개수는 $m$ 또는 $k$로 말하는 경우가 많습니다. 수학에서는 정점을 $V$ (Vertex), 간선을 $E$ (Edge)로 말하기도 합니다.

 

이제 간선 정보를 저장할 차례입니다. 어떤 두 점이 연결되어 있는지 저장하는 방식으로는 인접 행렬과 인접 리스트가 있습니다.

 

인접 행렬

인접 행렬은 크기 $n \times n$의 이차원 배열로, 인접 행렬의 $i$행 $j$열의 원소는 $i$번과 $j$번 정점을 잇는 간선이 있으면 1, 없으면 0으로 정하는 방법을 말합니다. 예를 들어 위에서 예시로 든 왼쪽 그래프에서는

 

위와 같은 인접 행렬을 얻을 수 있을 것입니다.

 

인접 행렬에는 치명적인 문제점이 있습니다. 먼저, 두 정점을 잇는 간선이 여러 개인 경우를 표현하지 못하는데, 이는 간선이 여러 개인 경우 1 대신 간선의 개수를 넣는 방식으로 해결할 수 있습니다. 하지만 진짜 문제는, 공간 낭비입니다. 잘 보시면, 이 인접 행렬에는 0인 원소가 정말로 많습니다. 하지만 인접 행렬을 사용하면 $O(V^2)$의 공간이 필연적으로 사용되기 때문에, 심각한 공간 낭비 현상이 발생할 수 있는 것이죠. 이러한 문제점을 해결한 것이 인접 리스트입니다.

 

인접 리스트

인접 리스트는 동적 배열(C++의 경우 vector)을 이용한 것으로, 어떤 정점 $i$에 대해 $i$번 정점과 인접한 정점의 목록을 동적 배열에 저장한 것을 말합니다.

 

위와 같은 방식으로 저장하는 것입니다. 인접 리스트는 인접 행렬과 달리 공간 복잡도가 $O(E)$로 메모리를 아낄 수 있지만, 최악의 단점은 두 정점이 연결되어 있는지 판별하는 데 매우 긴 시간이 걸린다는 것입니다. $i$, $j$번 정점이 서로 인접한지 판별하려면 $i$번 정점의 인접 리스트를 모두 순회해 봐야 한다는 것이죠.

 

따라서 이 두 방법은 모두 장단점을 가지고 있고, 경우에 따라서 둘 중 하나를 적절하게 선택하는 것이 좋습니다.

 

차수

무방향 그래프에서, 각 정점과 연결된 간선의 수를 차수(degree)라고 합니다. 유방향 그래프의 경우 정점으로 들어오는 간선과 정점에서 나가는 간선이 있는데, 정점으로 들어오는 간선의 수를 indegree, 정점에서 나가는 간선의 수를 outdegree라고 합니다.

 

위의 왼쪽 그림의 그래프에서 각 정점의 차수는 다음과 같습니다.

정점 번호 0 1 2 3 4 5
차수 3 2 3 1 4 3

 

여기서 모든 차수를 더해 봅시다. 3+2+3+1+4+3=16입니다. 이는 간선 개수의 두 배와 같네요. 왜일까요? 그것은 바로, 간선 하나가 차수를 2 증가시키기 때문입니다. 간선의 두 끝점의 차수를 1씩 올려주는 것이죠.

 

2번 정점과 4번 정점을 잇는 간선은 2번 정점의 차수와 4번 정점의 차수를 1씩 증가시킵니다.

이 성질은 어떻게 보면 당연하지만, 정말 유용합니다. 나중에 시간 복잡도의 증명에 활용하는 일이 생길 것입니다.

 

특이한 그래프

완전 그래프

모든 정점 쌍 사이에 간선이 있는 그래프를 말합니다. 완전 그래프의 정점이 $V$개라면, 간선은 $\frac{V(V-1)}{2}$개가 됩니다.[각주:2] 하지만 완전 그래프는 대회에서 출현 빈도가 높진 않습니다.

 

트리

사이클이 없는 연결 그래프를 말합니다. 그 특성상 정말 다양한 성질이 있는데, 트리에 대해서는 추후에 자세히 배울 예정입니다.

 

 

연습문제

BOJ 3098. 소셜 네트워크 (S4)

 

인접 행렬을 쓰는 문제입니다. 입력을 받은 뒤, $N \times N$ 크기 행렬을 만들어 mat[i][j]: (i, j번 사람이 친구 관계이면 1, 아니면 0)으로 정의합니다.

 

이후 3중 for문으로 시뮬레이션을 해 주면 늘어나는 친구 관계를 포착할 수 있습니다. 모든 사람이 서로 친구 관계가 되면 시뮬레이션을 멈춥니다. 시간 복잡도는 $O(N^4)$가 되는데, 그 이유는 모든 사람이 친구 관계가 되는 데 걸리는 시간이 $N$분 이하이기 때문입니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int mat[52][52], mat2[52][52];
int cnt;
vector<int> ans; // 하루에 늘어난 친구 쌍의 수를 관리합니다.

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++){
        int ts, te;
        scanf("%d %d", &ts, &te);
        mat[ts][te] = mat[te][ts] = 1; // 인접 행렬을 세팅합니다.
        mat2[ts][te] = mat2[te][ts] = 1;
        cnt += 2; // 서로 친구 관계인 쌍 수를 관리합니다. (같은 쌍은 두 번 셉니다)
    }
    
    while(cnt < n*(n-1)){ // 친구가 아닌 쌍이 있을 때까지 반복합니다.
        int tmp = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    if(i!=k && mat[i][j] && mat[j][k]){ // 만약 i-j, j-k가 서로 친구 관계라면, i-k도 친구 관계입니다.
                        mat2[i][k] = mat2[k][i] = 1;
                    }
                }
            }
        }
        
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(!mat[i][j] && mat2[i][j]) cnt++, tmp++; // 오늘 친구가 한 쌍 늘었습니다.
                mat[i][j] = mat2[i][j];
            }
        }
        
        ans.push_back(tmp / 2); // 출력할 수 목록에 오늘 늘어난 친구 쌍의 수를 추가합니다.
    }
    printf("%d\n", (int)ans.size()); // 지난 날의 수는 벡터의 크기와 같습니다.
    for(auto &x: ans){ // C++11에서 새로 추가된 문법으로, 벡터 ans의 모든 원소를 x에 대입하면서 순회하는 편리한 문법입니다.
        printf("%d\n", x); // 각 날에 친구 쌍이 몇 쌍 늘었는지 추가합니다.
    }
}

 

BOJ 11403. 경로 찾기 (S1)

 

위 문제와 거의 똑같은 방법으로 풀립니다. 어떻게 고치면 될까요?

더보기

while문 대신, N번 반복하는 for문으로 고치고, i=j인 경우도 1을 출력하게 고칩니다.

 

 

 

  1. 용량은 한 번에 간선을 지날 수 있는 최대 인원 수를 말한다고 생각하면 이해에 도움이 될 것입니다. 후반부에 network flow 등의 알고리즘 정도에서만 한정적으로 등장하는 개념이니 지금은 몰라도 좋습니다. [본문으로]
  2. 중등 수준의 수학 교육을 받으신 분은 왜인지 짐작하실 수 있을 겁니다. [본문으로]

'코딩 > 알고리즘' 카테고리의 다른 글

[초급] 그래프  (6) 2020.07.29
[초급] 비트마스크  (5) 2020.07.13
[초급] 백트래킹  (5) 2020.07.08
[초급] 정렬  (2) 2020.07.08
알고리즘 게시글 작성 계획  (4) 2020.07.08