[그래프] 정리

[jusung-c]

그래프(Graph)란?

자료 구조로써 Graph = 정점(Vertex) + 간선(Edge)

간선(Edge)의 종류

1. 무방향(양방향) 간선

2. 방향 간선

3. 무방향/방향 + 가중치

정점의 차수(Degree)

정점의 차수(Degree)는 정점에 연결된 간선의 개수를 뜻한다.

• 1번 정점의 차수: 3
• 4번 정점의 차수: 3

정점의 성질

모든 차수의 합을 더하면 간선의 개수의 2배가 된다!!

간선 하나는 두개의 정점을 잇는 것이므로 당연한 성질이다. 이 성질을 알아야 나중에 시간 복잡도 계산할 때 활용할 수 있다.

---

그래프를 저장하는 방법

사람은 그래프를 눈으로 보고 풀지만 컴퓨터는 그럴 수 없기 때문에 그래프를 저장하는 방법을 알아야 한다.

5개의 정점과 5개의 간선으로 이루어진 그래프

1. 인접 행렬 (Adjacency Matrix)

• 2차원 행렬로 표현
• 정점(V)의 제곱 개의 칸
• 두 정점 사이의 간선이 있으면 1, 없으면 0으로 표현
• adj[A, B] = 1 -> A에서 B로 향하는 간선이 있다.
• 만약 가중치가 생긴다면 가중치를 기록해주면 된다.

int[][] adj = int new [V][V];

행과 열은 각각 정점(V)의 개수만큼 필요하므로 O(V^2) 만큼의 공간이 필요하다.

정점의 개수가 V, 간선의 개수가 E 일 때 인접행렬로 간선을 관리하게 될 경우 각 정점마다 인접한 간선의 수가 모두 E일 수 있으므로 시간복잡도는 O(V*E)가 된다.

A에서 B로 향하는 간선이 존재하는 지 혹은 가중치가 얼마인지 확인하려면?

adj[A][B]에 저장된 값만 찾으면 되므로 O(1)의 시간밖에 걸리지 않는다.

만약 정점 A에서 갈 수 있는 정점들을 찾으려면 어떻게 해야할까?
A 행의 모든 값을 탐색하면서 값이 1인 경우를 찾으면 되므로 O(V) 시간 안에 답을 구할 수 있다.

정점 V가 10만개이고 간선 E가 50만개인 그래프를 저장하려면

V가 10만개이므로 V^2인 100억개의 공간이 필요하다. 100억은 10GB와 동일하기 때문에 만약 int 자료형으로 2차원 배열을 생성하게 되면 40GB나 필요하게 된다.
사실 100억개의 값 중 필요한 값은 값이 1인 경우인데 100억개 중 몇 개 안 될 것이다.. 실제 활용하는 공간은 매우 작으므로 공간의 활용도가 매우 낮은 것이다.

즉, 인접행렬은 구현하기엔 쉽지만 메모리 이슈가 생길 수 있다.

2. 인접 리스트 (Adjacency List)

인접 행렬의 메모리 이슈를 해결하기 위해 나온 것으로 정점마다 연결된 간선들만, 즉 필요한 값들의 공간만 생성하는 방법이다.

• 동적 배열을 정점의 개수만큼 잡는다. 정점이 5개였으므로 5개의 동적 배열
• adj[A] = {B1, B2, B} -> A에서 B1, B2, B3로 향하는 간선이 존재한다.

ArrayList<ArrayList<Integer>> adj;

각 정점마다 연결된 간선의 개수만큼 공간을 사용한다. 즉, 정점의 차수만큼의 크기가 필요하다.
모든 정점의 차수의 합은 간선의 2배이므로 필요한 공간의 크기는 총 O(E)이다.

정점의 개수가 V, 간선의 개수가 E일 때 간선을 인접 리스트로 관리할 때의 시간 복잡도는 모든 간선을 한 번씩 순회하면서 각 정점마다 인접한 간선을 저장하기 위해 O(1)의 시간이 걸리기 때문에 총 O(E+V)이다.

• 정점 생성: O(V)
• 간선 처리: O(E) * O(1) = O(E)
• 전체 시간 복잡도: O(V) + O(E) = O(V + E)

A에서 B로 향하는 간선이 존재하는 지 혹은 가중치가 얼마인지 확인하려면?

ArrayList A를 탐색해 B가 존재하는 지 확인한다.

• 양방향(무방향) 그래프라면 A와 B 리스트 중 리스트의 크기가 더 작은, 즉 차수가 작은 리스트에서 탐색을 진행하면 되므로 시간 복잡도는 O(min(deg(A), deg(B))이다.
• 방향 그래프라면 무조건 A를 탐색해 B가 존재하는 지 확인하면 된다. 시간 복잡도는 O(deg(A))이다.

만약 정점 A에서 갈 수 있는 정점들을 찾으려면 어떻게 해야할까?

• A 리스트를 모두 탐색해보면 되므로 O(deg(A))의 시간이 걸린다.

정점 V가 10만개이고 간선 E가 50만개인 그래프를 저장하려면?

V가 10만이고 E가 50만이기 때문에 필요한 공간은 O(E)라서 50만개의 공간 만큼만 있으면 된다!

정리

각 경우마다 빠른 방법이 다르므로 문제를 보고 그래프를 어떻게 저장할 지 생각해야 한다. 또한 인접 행렬이 더 빠르더라도 메모리 이슈가 생길 수 있기에 공간 복잡도를 잘 고려해서 생각해야 한다.

---

그래프 문제의 핵심

1. 정점(V) & 간선(E)에 대한 정확한 정의

문제에서 정점과 간선을 명확히 주지 않을 때도 있다. 어떤 정보들이 정점과 간선에 대응되는 것인지 파악할 필요가 있다.
ex) 1번 마을에서 5번 마을로 이동 -> 1번 정점에서 5번 정점 잇는 간선

---

2. 간선 저장 방식 판단

인접 행렬을 쓸지 인접 리스트를 쓸지 판단해야 한다.

대부분의 경우 인접 리스트를 사용하긴 한다.

그래프에서 탐색이란?

탐색(Search) = 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가?

2가지 정보가 주어진다.

1. 그래프
2. 시작점

탐색을 하고자 하는 목적은 시작점에서 시작해 간선을 이용해 갈 수 있는 모든 정점을 찾는 것이다.
사람은 그냥 저 위의 그래프만 보고 4에서 시작하면 1, 3에 갈 수 있겠구나 생각하지만 컴퓨터 입장에서는 위 그래프를 아래 인접 리스트로 저장하기 때문에 다른 접근이 필요하다.

1. 탐색 결과, 즉 갈 수 있으면 true, 없으면 false를 나타내는 배열을 만든다.

2. 탐색을 통해 결과 배열을 채운다.

---

그래프 탐색 알고리즘

1. 깊이 우선 탐색 (Depth First Search)

재귀 함수를 이용

		// x를 갈 수 있다는 걸 알고 방문한 상태
    static void dfs(int x) {
        // x 방문
        visit[x] = true;
        
        // x 에서 갈 수 있는 곳들을 모두 방문
        for(int y : x에서 갈 수 있는 점들) {
            // y를 이미 갈 수 있다는 사실을 안다면 굳이 방문 안함.
            if(visit[y]) continue;
            
            // y에서 갈 수 있는 곳들도 전부 확인
            dfs(y);
        }
    }


		main() {
				dfs(시작점);
		}

그래프가 인접 리스트로 저장되어 있고, 시작점이 5인 경우

1. 입력받은 순서대로 먼저 4번으로 이동
2. 이동 후 이동했다는 방문 체크

4. 5번은 이미 방문 체크 되어 있으므로 무시하고 1번으로 이동

5. 4, 5번은 이미 방문했으므로 무시하고 2번으로 이동

6. 5번, 1번 모두 방문했으므로 무시한다. dfs(2) 함수가 종료되면서 dfs(2)를 호출했던 dfs(1)로 돌아간다.

7. 5번도 이미 방문했으므로 dfs(1)이 종료되면서 dfs(1)을 호출했던 dfs(4)로 돌아가고 마찬가지로 dfs(4)가 종료되면서 호출했던 dfs(5)로 돌아간다.

8. dfs(5)로 돌아와서 2, 4번은 방문했으므로 3번을 방문한다.

9. 위의 과정이 반복되어 마지막 dfs(5)까지 종료되면 탐색이 완료된다.

이를 코드로 다시 살펴보자

총 시간 복잡도는 인접행렬은 O(V^2)이고 인접 리스트는 O(deg(1) + deg(2) + … + deg(V))이다. 차수의 총 합은 간선의 개수의 2배이므로 O(E)와 같다.

따라서 DFS의 경우 V^2이 E보다 월등히 큰 그래프라면 인접 리스트로 그래프를 저장해 접근하는 것이 더 빠를 것이다.

2. 너비 우선 탐색 (Breadth First Search)

static void bfs(int start) {
    Queue<Integer> que = new LinkedList<>();

    // start는 방문 가능한 점이므로 que에 넣어준다.
    que.add(start);

    // start는 늘 갈 수 있다고 표시 (중요!!)
    visit[start] = true;

    // 더 확인할 점이 없다면 정지
    while (!que.isEmpty()) {
        int x = que.poll();

        for (int y : x에서 갈 수 있는 점들) {
            // x 에서 y 를 갈 수 있지만, 이미 방문했다면 무시
            if (visit[y]) continue;

            // y를 갈 수 있으니까 que에 추가하고 visit 처리
            que.add(y);
            visit[y] = true;
        }
    }
}

Queue가 들고 있는 자료의 의미는?
방문이 가능한 정점들을 찾을 때, Queue에 해당 정점을 넣는다.

1. Queue에 정점이 남은 경우 -> 아직 방문 가능한 점이 남아있거나 탐색이 끝나지 않은 상태이다.
2. Queue가 비어있는 경우 -> 시작점에서 갈 수 있는 모든 점을 찾아냈거나 탐색이 종료된 상태이다.

그래프가 인접 리스트로 저장되어 있고 시작점이 2인 경우

1. 시작점인 2를 Queue에 넣고 방문처리 해준 상태에서 시작한다.

2. 2에서 갈 수 있는 정점들을 탐색 후 아직 방문하지 않은 정점들을 모두 Queue에 넣은 후 방문처리한다.

3. 큐에서 다음 정점을 뽑아온다. 현재는 1에 해당한다. 1을 큐에서 제거한 후 1에서 갈 수 있는 정점 중 아직 방문하지 않은 정점들을 모두 큐에 넣은 후 방문 처리한다.

4. 위 과정을 반복해 방문할 수 있는 모든 곳들을 방문한다.

만약 방문 체크를 Queue에 넣으면서 해주지 않고 Queue에서 뽑을 때마다 해준다면 어떻게 될까?

static void bfs(int start) {
    Queue<Integer> que = new LinkedList<>();

    // start는 방문 가능한 점이므로 que에 넣어준다.
    que.add(start);

    // start는 늘 갈 수 있다고 표시 (중요!!)
		visit[start] = true;

    // 더 확인할 점이 없다면 정지
    while (!que.isEmpty()) {
        int x = que.poll();
        visit[x] = true;     // 요기서 방문 체크를 하면?

        for (int y : x에서 갈 수 있는 점들) {
            // x 에서 y 를 갈 수 있지만, 이미 방문했다면 무시
            if (visit[y]) continue;

            // y를 갈 수 있으니까 que에 추가하고 visit 처리
            que.add(y);
            // visit[y] = true;
        }
    }
}

탐색을 끝까지 해보면 답은 구할 수 있지만 다음과 같은 그래프에서는 시간이 매우 오래 걸릴 수 있다.

1에서 시작한다고 했을 때 큐에 1이 들어간 후 1을 빼면서 방문처리를 한다.

그 후 2, 3을 넣은 다음에 2를 빼면서 방문처리를 한다.
그 후 4, 5를 넣은 다음에 3를 빼면서 방문처리를 한다.
그 후 4, 5를 넣은 다음에 4를 빼면서 방문처리를 한다.

…

이렇게 하다보면 계속 반복해서 큐에 넣었던 수를 넣게 된다.

따라서 한번 방문을 한 시점에 방문 처리를 하지 않으면 같은 정점이 큐에 여러번 들어갈 수 있기 때문에 시간이 훨씬 오래 걸린다.

---

문제의 특징 별 DFS / BFS 활용

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관이 없다.

2. 경로의 특징을 저장해둬야 하는 문제

예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)

3. 최단거리를 구하는 문제

미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다.

왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

이외에도 검색 대상 그래프가 정말 크다면 DFS를 고려하고 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려하는 등으로 더 생각해볼 수 있다.

DFS, BFS 시간 복잡도