알고리즘) 그래프(Graph)

그래프 문제는 문제에 나와 있는 상황을 그래프로 모델링해서 푼다.

어떻게 문제의 상황을 그래프로 만드는지가 관건!

 

# 그래프는 G = (V, E)로 나타낸다.

V는 vertex(정점) E는 Edge(간선)의 약자

 

# 사이클 : 정점 A에서 다시 정점 A로 돌아오는 경오

 

# 단순 경로, 단순 사이클 (Simple Path, Simple Cycle)

- 경로, 사이클에서 같은 정점을 2번 이상 방문하지 않는 경로, 사이클이다

- 일반적으로 경로, 사이클로 적혀있을 경우, 이를 의미한다.

 

# 방향 있는 그래프, 방향 없는 그래프 (Directed/Undirected Graph)

- 간선들에 방향이 있으면 directed, 없으면 undirected이다.

 

# 가중치(Weight)

- 간선의 값이다.

- 주로 간선에 해당하는 거리, 시간, 비용을 나타내는데 사용된다.

- 별도로 설정되어 있지않으면 기본적으로 모든 간선의 가중치는 1이다.

 

# 차수(Degree)

- 정점과 연결되어 있는 간선정의 개수

- directed 그래프에서는 이를 in-degree, out-degree로 정점에 들어오는 간선인지, 정점에서 나가는 간선인지 구분하기도 한다.

 

# 그래프를 어떻게 저장하는가? -> 정점과 간선을 저장해야한다.

- 정점 : 정점의 개수를 통해 저장한다. 

   정점이 총 6개라면 각 정점 이름을 0, 1, 2, 3, 4, 5로 설정해서 저장

- 간선 : 정점과 같이 개수로 저장되면 만들 수 있는 그래프의 경우의 수가 다수 존재한다 -> 해당 방법 부적합

 

위와 같은 간선의 특징 때문에 간선을 저장하는 방법이 포인트가 된다.

그리고 한 정점 x와 연결된 간선을 효율적으로 찾는 구조로 그래프를 저장하는 것이 중요하다.

 

# 그래프 저장 방법

 1. 인접 행렬

 2. 인접 리스트

 

# 인접 행렬

정점의 개수를 V라고 했을 때 

V*V 크기의 2차원 배열을 사용하여 그래프를 저장한다.

간선이 있으면, A[i][j] = 1 (가충치가 있다면 가충치의 값)

간선이 없으면, A[i][j] = 0으로 값을 할당한다.

(i, j는 간선 1개를 잇는 2개의 정점을 나타낸다.)

 

인접 행렬을 사용하면 그래프를 저장하는데 V^2 만큼의 공간이 요구된다.

한 정점에 연결된 모든 정점을 구하는 시간복잡도는 O(V)이다.

 

# 인접 리스트

리스트를 이용해서 그래프를 저장한다.

A[i] = j 꼴로 각 정점에 연결되어 있는 정점들을 저장하는 방식으로 간선을 저장한다.

(i, j는 각 정점들을 의미한다.)

리스트 자료구조를 사용하는 이유는 각 정점에 몇 개의 정점이 연결되어 있는지 알 수 없기 때문에

개수 제한 없이 원소 추가가 가능한 리스트를 사용하는 것이다.)

 

일반적으로 LinkedList을 이용해서 구현하며

C++은 vector, JAVA는 Arraylist, Python은 List[] 자료구조를 사용해서 구현한다.

 

# 공간 복잡도

인접 행렬 : O(V^2)

인접 리스트 : O(E)

(V는 정점의 개수, E는 간선의 개수)

 - 인접 행렬은 존재하지 않는 간선에 대한 메모리도 할당되지만, 

   인접 리스트는 존재하는 간선에 대해서만 메모리가 할당되기 때문이다.

(인접 리스트의 경우, 한 정점에 연결된 모든 간선을 찾는 시간복잡도는 O(차수)이다.

 

인접 리스트가 인접 행렬보다 시간적, 공간적으로 효율적이기 때문에

인접 리스트가 더 빈번하게 사용된다.

cf) 임의의 두 정점 사이에 간선이 존재하는지 구하는 경우에만 인접 행렬이 더 유리하다.

    인접 행렬은 각 정점을 잇는 간선을 저장하는 메모리에 접근하여 값이 0이 아닌지 확인하면 되지만(O(1))

    인접 리스트는 해당 정점에 연결된 모든 정점들을 확인해야(O(E)) 이를 판별할 수 있기 때문이다. 

 

다음 코드는 백준 13023번 문제를 해결하기 위해

인접 행렬, 인접 리스트, 간선 리스트를 사용한 코드이다.

 

import java.util.*;
class Edge { // 간접 리스트를 위한 클래스
    int from, to;
    Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 사람 수
        int m = sc.nextInt(); // 관계 수

        boolean[][] a = new boolean[n][n]; // 인접 행렬 구현
        ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; // 인접 리스트 구현
        ArrayList<Edge> edges = new ArrayList<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        for (int i=0; i<m; i++) {
            // 친구 관계는 양방향 관계이므로 양 방향으로 간선을 배정해야 한다.
            // 간선 리스트에 관계 저장
            int from = sc.nextInt();
            int to = sc.nextInt();
            edges.add(new Edge(from, to));
            edges.add(new Edge(to, from));
            // 인접 행렬에 관계 저장
            a[from][to] = a[to][from] = true;
            // 인접 리스트에 관계 저장
            g[from].add(to);
            g[to].add(from);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 2개의 간선들에 대한 관계 파악해줌
        for (int i=0;i<m;i++) {
            for (int j=0;j<m;j++) {
                // 간선리스트 사용
                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/13023