Dijkstra Algorithm: 택배 배송 In Java

택배 배송 문제를 다익스트라 알고리즘을 사용하여 해결하는 방법을 알아봅니다. 이 글에서는 인접 리스트, 최단 거리 배열, 우선순위 큐 등의 핵심 기능들을 어떻게 활용하는지 자세히 설명하고, compare 비교 로직을 람다식, Integer.compare(), Comparable 인터페이스 구현을 통해 다양하게 구현하는 방법을 소개합니다. 자바 코드를 통해 각 방법을 명확하게 이해하고, 실제 코딩 테스트에서 효율적으로 적용할 수 있도록 돕는 것을 목표로 합니다.

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 대표적인 알고리즘 중 하나입니다. 특히, 가중치가 있는 그래프에서 특정 시작 노드에서 다른 모든 노드까지의 최단 거리를 효율적으로 계산할 수 있습니다. 이 알고리즘은 택배 배송 문제와 같이 최적의 경로를 찾아야 하는 상황에서 매우 유용하게 활용됩니다. 예를 들어, 여러 도시를 연결하는 도로망에서 특정 도시에서 다른 모든 도시로 가는 가장 짧은 경로를 찾는 데 사용할 수 있습니다.

다익스트라 알고리즘의 핵심 아이디어는 다음과 같습니다.

1. 시작 노드에서 출발하여 방문하지 않은 노드 중 현재까지 계산된 거리가 가장 짧은 노드를 선택합니다.
2. 선택된 노드를 방문하고, 해당 노드와 연결된 다른 노드들의 거리를 갱신합니다. 이때, 현재까지 알려진 거리보다 선택된 노드를 거쳐서 가는 거리가 더 짧다면 해당 거리로 갱신합니다.
3. 모든 노드를 방문하거나, 더 이상 방문할 노드가 없을 때까지 위의 과정을 반복합니다.

이러한 과정을 통해 시작 노드에서 모든 노드까지의 최단 거리를 구할 수 있습니다. 다익스트라 알고리즘은 우선순위 큐를 사용하여 방문할 노드를 효율적으로 관리하며, 시간 복잡도를 O(E log V)로 최적화할 수 있습니다. 여기서 E는 간선의 수, V는 노드의 수를 의미합니다.

사용된 기능들

택배 배송 문제를 해결하기 위해 다음과 같은 기능들이 사용됩니다.

Compare 비교 로직

우선순위 큐를 사용할 때, 노드 간의 우선순위를 결정하기 위해 비교 로직이 필요합니다. 자바에서는 Comparator 인터페이스를 구현하거나 람다식을 사용하여 비교 로직을 정의할 수 있습니다. 여기서는 다양한 방법으로 비교 로직을 구현하는 방법을 살펴보겠습니다.

1. 람다식 + 명시적 변환

람다식을 사용하여 비교 로직을 간결하게 표현할 수 있습니다. 다음은 람다식을 사용하여 items 배열을 score를 기준으로 정렬하는 예제입니다.

Arrays.sort(items, (a, b) -> {
    if (a.score < b.score) return -1;
    if (a.score > b.score) return 1;
    return 0;
});

여기서 (a, b)는 비교할 두 객체를 나타내며, return 값이 음수일 경우 오름차순 정렬, 양수일 경우 내림차순 정렬을 의미합니다. 이 방식을 활용하여 다음과 같이 여러 기준으로 정렬할 수 있습니다.

1-1. 다중 조건 정렬

Arrays.sort(meetings, (m1, m2) -> {
    // 종료 시간이 같을 경우 (제2 기준)
    if (m1[1] == m2[1]) {
        return m1[0] - m2[0]; // 시작 시간 오름차순
    }
    // 종료 시간이 다를 경우 (제1 기준)
    return m1[1] - m2[1]; // 종료 시간 오름차순
});

위 코드는 meetings 배열을 종료 시간을 기준으로 오름차순 정렬하고, 종료 시간이 같을 경우 시작 시간을 기준으로 오름차순 정렬합니다.

1-2. 절댓값 기준 정렬

PriorityQueue<Integer> pQueue = new PriorityQueue<>((a, b) -> {
    int absA = Math.abs(a);
    int absB = Math.abs(b);

    if (absA != absB) {
        // 1순위: 절댓값이 작은 쪽 (absA - absB는 absA가 작을 때 음수를 반환해 우선)
        return absA - absB;  // 양수면 B우선, 음수면 A 우선
    } else {
        // 2순위: 절댓값이 같으면 실제 값이 작은 쪽 (a - b는 a가 작을 때 음수를 반환해 우선)
        return a - b;
    }
});

위 코드는 절댓값이 작은 순서대로 정렬하고, 절댓값이 같을 경우 실제 값이 작은 순서대로 정렬합니다.

2. 람다식 + Integer.compare() (Long.compare()) 사용

Integer.compare() 또는 Long.compare()를 사용하면 비교 로직을 더욱 간결하게 표현할 수 있습니다. 이 메서드는 두 값을 비교하여 결과를 반환하므로, 직접 음수 또는 양수를 반환할 필요가 없습니다.

// 오름차순
PriorityQueue pq = new PriorityQueue<>((e1, e2) -> Long.compare(e1.cost, e2.cost)); 
// 내림차순
PriorityQueue pq = new PriorityQueue<>((e1, e2) -> Long.compare(e2.cost, e1.cost)); // compare의 순서만 변경

위 코드는 cost를 기준으로 오름차순 또는 내림차순으로 정렬합니다. Long.compare()의 인자 순서를 변경하면 정렬 순서를 쉽게 바꿀 수 있습니다.

3. 클래스 자체에 Comparable 구현

Comparable 인터페이스를 구현하면 클래스 자체가 비교 기능을 내장하게 됩니다. 이를 통해 객체 간의 비교 로직을 클래스 내부에서 정의할 수 있습니다.

class Edge implements Comparable<Edge> {
    int to;
    long cost;
    Edge(int to, long cost) {
        this.to = to;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge other) {
        if(this.cost < other.cost) return -1;
        if(this.cost > other.cost) return 1;
        return 0;
        // 또는 return  Long.compare(this.cost, other.cost);
        // 내림차순 return Long.compare(other.cost, this.cost);
    }
}

위 코드는 Edge 클래스가 Comparable 인터페이스를 구현하여 compareTo() 메서드를 오버라이드합니다. 이를 통해 Edge 객체 간의 비교 로직을 정의할 수 있으며, PriorityQueue와 같은 컬렉션에서 자동으로 정렬 기능을 사용할 수 있습니다.

결론

택배 배송 문제와 같은 최단 경로 찾기 문제에서 다익스트라 알고리즘은 매우 효과적인 해결책을 제공합니다. 인접 리스트, 최단 거리 배열, 우선순위 큐와 같은 자료구조와 알고리즘을 적절히 활용하고, compare 비교 로직을 다양하게 구현함으로써 효율적인 코드를 작성할 수 있습니다. 람다식, Integer.compare(), Comparable 인터페이스 구현 등 다양한 방법을 통해 비교 로직을 구현하는 방법을 익히면, 실제 코딩 테스트에서 더욱 유연하게 대처할 수 있을 것입니다. 이러한 기술들을 숙지하고 연습하여, 다익스트라 알고리즘을 자유자재로 활용할 수 있도록 노력합시다!