자바 코딩테스트 강좌, 그래프의 표현

안녕하세요! 오늘은 자바를 사용하여 코딩테스트에 자주 출제되는 그래프의 표현에 대해 자세히 알아보고, 관련된 알고리즘 문제를 풀어보겠습니다. 그래프는 주어진 문제를 해결하는데 중요한 데이터 구조로, 정점(Vertex)과 간선(Edge)으로 구성됩니다. 우리는 여러 가지 방식으로 그래프를 표현할 수 있으며, 이번 글에서는 Adjacency List와 Adjacency Matrix 방식에 대해 설명하겠습니다.

그래프의 표현 방식

1. 인접 리스트(Adjacency List)

인접 리스트는 각 정점이 인접한 정점의 목록을 저장하는 방식입니다. 보통 배열이나 리스트를 사용하여 구현합니다. 이 방식은 메모리 효율성이 매우 뛰어나며, 다소 느리게 진행되는 연산에서도 유용합니다.

class Graph {
    private int vertices; // 정점의 수
    private LinkedList[] adjList; // 인접 리스트
    
    // 그래프 생성자
    public Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 간선 추가 메소드
    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
        // 무방향 그래프인 경우, 다음 코드도 추가해야 합니다
        // adjList[destination].add(source);
    }
}

2. 인접 행렬(Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방식입니다. 이 방법은 간선이 존재하는지 여부를 O(1)의 시간 복잡도로 확인할 수 있지만, 공간 복잡도가 높고, 가변 크기의 그래프에서는 비효율적일 수 있습니다.

class Graph {
    private int vertices;
    private int[][] adjMatrix;

    // 그래프 생성자
    public Graph(int v) {
        vertices = v;
        adjMatrix = new int[v][v];
    }

    // 간선 추가 메소드
    public void addEdge(int source, int destination) {
        adjMatrix[source][destination] = 1;
        // 무방향 그래프인 경우
        // adjMatrix[destination][source] = 1;
    }
}

문제: 다리 만들기

이제 실제로 문제를 풀어보겠습니다. 주어진 문제는 다리 만들기입니다.

문제 설명

2D 평면에서 N개의 점이 주어지고, 모든 점이 서로 연결될 수 있도록 다리를 건설하고자 합니다.
다리의 길이는 두 점 사이의 유클리드 거리입니다.
가장 짧은 경로의 길이를 구하세요. 단, 다리를 건설하는 과정에서 같은 두 점을 다시 연결할 수 없습니다.

입력

첫 번째 줄에 점의 개수 N(1 ≤ N ≤ 100) 이 주어집니다.
두 번째 줄에 각 점의 좌표가 주어집니다. (x1, y1), (x2, y2), …, (xN, yN)

출력

가장 짧은 경로의 길이를 출력하시오. (소수점 아래 2자리까지)

문제 풀이 접근

문제를 해결하기 위해 다음과 같은 순서로 접근하겠습니다:

좌표를 입력받아 점들을 저장합니다.
좌표들 사이의 거리를 계산하여 다리 길이를 구합니다.
Dijkstra 알고리즘을 사용하여 최단 경로를 구합니다.
결과를 소수점 둘째자리까지 출력합니다.

자바 코드 구현

import java.util.*;

class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    double distance(Point p) {
        return Math.sqrt(Math.pow(this.x - p.x, 2) + Math.pow(this.y - p.y, 2));
    }
}

class Graph {
    private int vertices;
    private List points;
    private double[][] adjMatrix;

    public Graph(int v) {
        vertices = v;
        points = new ArrayList<>();
        adjMatrix = new double[v][v];
    }

    public void addPoint(Point p) {
        points.add(p);
        int idx = points.size() - 1;
        for (int i = 0; i < idx; i++) {
            double dist = points.get(i).distance(p);
            adjMatrix[i][idx] = dist;
            adjMatrix[idx][i] = dist; // 무방향 간선
        }
    }

    public double dijkstra() {
        double[] dist = new double[vertices];
        boolean[] visited = new boolean[vertices];

        Arrays.fill(dist, Double.MAX_VALUE);
        dist[0] = 0; // 시작점

        for (int i = 0; i < vertices - 1; i++) {
            int minIndex = findMinIndex(dist, visited);
            visited[minIndex] = true;

            for (int j = 0; j < vertices; j++) {
                if (!visited[j] && adjMatrix[minIndex][j] != 0 &&
                    dist[minIndex] + adjMatrix[minIndex][j] < dist[j]) {
                    dist[j] = dist[minIndex] + adjMatrix[minIndex][j];
                }
            }
        }

        return dist[vertices - 1]; // 끝점까지의 거리
    }

    private int findMinIndex(double[] dist, boolean[] visited) {
        double min = Double.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Graph graph = new Graph(n);

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.addPoint(new Point(x, y));
        }

        double result = graph.dijkstra();
        System.out.printf("%.2f\n", result);
    }
}

결론

오늘은 그래프의 표현 방식과 함께 알고리즘 문제를 풀어보았습니다.
이 문제를 통해 그래프를 어떻게 다루는지, 인접 리스트와 인접 행렬을 활용하여 점 사이의 거리 계산 및 최단 경로 알고리즘을 구현하는 방법을 배웠습니다.
그래프는 실생활에서도 자주 사용되는 개념이며, 더 나아가 복잡한 문제를 해결하는 데 매우 유용합니다.

다음 시간에는 탐색 알고리즘과 관련된 내용을 살펴보도록 하겠습니다. 감사합니다!