[Algorithm/Study] 6주차 - 그래프

 

해당 스터디는 <코딩 테스트 합격자 되기 C++> 저자님과 함께하는 스터디입니다.

인프런 강의 < 코딩 테스트 합격자 되기 C++ > 을 보고 정리한 내용입니다.

---

 

이번주 스터디 주제는 그래프이다. 그래프에 관해 간단하게 정리해둔 예전 포스팅도 있어서 같이 첨부해놓았다. 그래프 문제는 머리로는 이해해도 문제로 풀려고 하면 잘 풀리지 않는다. 문제를 많이 풀어봐야할 것 같다..🙄

[CS 발표_13] 그래프의 개념, 그래프 구현 방법

그래프의 개념

• 그래프 : 노드와 간선을 이용한 비선형 자료구조로 목적에 따라 선의 가중치나 방향이 있을 수 있다.
• 노드 : 값이 있는 점
• 간선 : 노드와 노드를 잇는 선

그래프의 종류

• 가중치가 있는 그래프
• 가중치가 없는 그래프
• 방향성 그래프
• 순환 그래프
• 비순환 그래프

그래프의 구현 - 인접 행렬

• 보통 인접 행렬은 2차원 배열로 나타낸다.
• 행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 된다.
• 노드 대비 간선이 적을 경우 메모리 공간 효율이 좋지않다.(노드 100개, 간선 1개인 경우에도 100 x 100 행렬이 필요)
• 특정 노드 사이 간선 존재 여부를 한 번에 알 수 있다.

그래프의 구현 - 인접 리스트

• 특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식이다.
• 실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비가 없다.
• 특정 노드에 모든 노드가 연결된 경우, 탐색 시 드물게 O(N)이 될 수 있다.

인접 행렬 vs 인접 리스트

노드의 개수가 많을 때 인접 행렬을 쓴다면 메모리가 초과할 가능성이 있으므로 인접 리스트를 써야한다. 특정 정점의 간선을 찾는 경우가 많으면 인접 행렬을 고려해본다.

 

• 인접 행렬
  • 공간 복잡도는 O(V²)이다. 모든 정점 간의 관계를 2차원 배열에 저장하므로, 정점 개수의 제곱에 비례하는 공간을 사용한다.
  • 특정 정점의 간선을 찾는 경우에는 O(1)이다. 배열을 통해 바로 접근할 수 있으므로, 특정 간선을 찾는 데 상수 시간이 걸린다.
  • 그래프의 모든 간선을 찾는 경우에는 O(V²)이다. 모든 정점 간의 간선을 확인해야 하므로 V²에 비례하는 시간이 걸린다.
• 인접 리스트
  • 공간 복잡도는 O(V + E)이다. 정점 개수와 간선 개수에 비례하는 공간을 사용한다.
  • 특정 정점의 간선을 찾는 경우에는 O(E)이며, 대부분은 O(E/V)이다. 인접 리스트를 순회해야 하므로, 최악의 경우 간선 전체를 확인해야 하고, 평균적으로는 O(E/V) 정도의 시간이 소요된다.
  • 그래프의 모든 간선을 찾는 경우에는 O(V + E)이다. 모든 정점과 간선을 확인하므로, V + E에 비례하는 시간이 걸린다.

깊이우선탐색 / 너비우선탐색

• 깊이 우선 탐색(DFS)
  • 더 이상 탐색할 노드가 없을 때까지 일단 간다.
  • 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드 퇴각 후(=백트래), 가지 않은 노드를 방문한다.
  • 스택 활용 → 함수의 호출 흐름과 동일하기 때문에 간단히 재귀함수로 구현하는 경우가 많다.
• 너비 우선 탐색(BFS)
  • 현재 위치에서 가장 가까운 노드부터 방문하고 다음 노드로 넘어간다.
  • 모든 노드를 방문할 때까지 위 과정을 반복한다.
  • 큐 활용 → 시작 노드 추시, 팝 이후 방문 처리하고 현재 노드에서 연결된 노드 중 방문하지 않은 노드 모두 푸

다음은 DFS와 BFS를 자바로 구현한 예제이다.

import java.util.*;

class Graph {
    private int vertices; // 그래프의 정점 개수
    private LinkedList<Integer>[] adjList; // 인접 리스트 배열

    // 그래프 생성자
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 간선 추가 메서드 (무방향 그래프)
    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
        adjList[destination].add(source); // 무방향 그래프일 경우 양쪽에 추가
    }

    // DFS (깊이 우선 탐색)
    public void DFS(int startVertex) {
        boolean[] visited = new boolean[vertices];
        DFSUtil(startVertex, visited);
    }

    private void DFSUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int neighbor : adjList[vertex]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }

    // BFS (너비 우선 탐색)
    public void BFS(int startVertex) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

최소경로 알고리즘

다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최단경로를 찾는 알고리즘이다. 우선순위 큐를 이용해 최단 경로를 효율적으로 계산할 수 있다. 다익스트라 알고리즘을 알면 벨만포드 알고리즘은 자동으로 따라오게 된다!

 

• 시작 정점에서 다른 모든 정점까지의 거리를 무한대로 초기화하고, 시작 정점의 거리를 0으로 설정한다.
• 현재 정점에서 이동할 수 있는 인접 정점들을 확인하고, 현재 정점을 거쳐서 가는 것이 더 짧다면 해당 정점까지의 거리를 갱신한다.
• 갱신한 후에는 우선순위 큐를 이용해 가장 짧은 거리를 가진 정점을 선택해 탐색을 진행한다.
• 모든 정점의 거리가 갱신될 때까지 위 과정을 반복한다.

다음은 다익스트라 알고리즘을 자바로 구현한 예제이다.

import java.util.*;

class Node implements Comparable<Node> {
    int vertex;
    int weight;

    public Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node other) {
        return this.weight - other.weight; // 가중치 오름차순 정렬
    }
}

public class DijkstraAlgorithm {
    private static final int INF = Integer.MAX_VALUE; // 무한대를 나타내는 값

    public static void dijkstra(List<List<Node>> graph, int start) {
        int vertices = graph.size();
        int[] distance = new int[vertices];
        Arrays.fill(distance, INF); // 모든 거리 값을 무한대로 초기화
        distance[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentVertex = current.vertex;
            int currentWeight = current.weight;

            // 현재 거리보다 더 긴 경로를 통해 온 경우 무시
            if (currentWeight > distance[currentVertex]) continue;

            // 인접한 노드 확인
            for (Node neighbor : graph.get(currentVertex)) {
                int nextVertex = neighbor.vertex;
                int weight = neighbor.weight;
                int newDist = distance[currentVertex] + weight;

                // 더 짧은 경로가 발견되면 거리 갱신
                if (newDist < distance[nextVertex]) {
                    distance[nextVertex] = newDist;
                    pq.add(new Node(nextVertex, newDist));
                }
            }
        }

        // 결과 출력
        System.out.println("정점 " + start + "으로부터의 최단 거리:");
        for (int i = 0; i < vertices; i++) {
            if (distance[i] == INF) {
                System.out.println("정점 " + i + "까지의 거리: 도달 불가");
            } else {
                System.out.println("정점 " + i + "까지의 거리: " + distance[i]);
            }
        }
    }

    public static void main(String[] args) {
        int vertices = 6; // 그래프의 정점 수
        List<List<Node>> graph = new ArrayList<>();

        // 그래프 초기화
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가 (무방향 그래프가 아니므로 한쪽 방향으로만 추가)
        graph.get(0).add(new Node(1, 7));
        graph.get(0).add(new Node(2, 9));
        graph.get(0).add(new Node(5, 14));
        graph.get(1).add(new Node(2, 10));
        graph.get(1).add(new Node(3, 15));
        graph.get(2).add(new Node(3, 11));
        graph.get(2).add(new Node(5, 2));
        graph.get(3).add(new Node(4, 6));
        graph.get(4).add(new Node(5, 9));

        // 시작 정점에서 다른 정점까지의 최단 거리 계산
        dijkstra(graph, 0); // 시작 정점을 0으로 설정
    }
}

 

 

[지금 무료]코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런