DP(Dynamic Programming) - 자바(JAVA)

DP는 다양한 문제에서 사용되는 효율적인 알고리즘 기법 중 하나이다.

 

코딩테스트 문제를 풀다가 최단 경로 문제에 DP의 필요성을 알게 돼서 DP에 대해 정리해 본다.

 

최단 경로 문제는 출발지에서 도착지까지 가는 경로 중 가장 짧은 경로를 찾는 문제로, 다익스트라 알고리즘과 벨만-포드 알고리즘이 대표적인 예시이다.

DP 배열은 중복 계산을 피하기 위해 사용되며, 최단 경로 문제에서는 각 노드까지의 최단 거리를 저장하는 역할을 하고, 각 노드까지의 최단 거리를 DP 배열에 저장하면 다음 계산에서 이전 계산 결과를 활용하여 중복 계산을 피할 수 있다.

아래는 최단 경로 문제를 DP 배열로 해결하는 다익스트라 알고리즘을 사용하여 출발지에서 각 노드까지의 최단 거리를 구하는 예시 코드이다. 

 

import java.util.Arrays;
import java.util.PriorityQueue;

public class ShortestPath {
    static int INF = Integer.MAX_VALUE; // 무한대를 표현하기 위한 값

    static void dijkstra(int[][] graph, int[] distance, int start) {
        int n = graph.length;

        Arrays.fill(distance, INF); // DP 배열 초기화
        distance[start] = 0; // 출발지까지의 거리는 0

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

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int node = cur.node;
            int dist = cur.distance;

            // 이미 처리된 노드라면 무시
            if (distance[node] < dist) {
                continue;
            }

            // 인접한 노드들을 순회하며 최단 거리 갱신
            for (int i = 0; i < n; i++) {
                if (graph[node][i] != 0 && distance[i] > dist + graph[node][i]) {
                    distance[i] = dist + graph[node][i];
                    pq.offer(new Node(i, distance[i]));
                }
            }
        }
    }

    static class Node implements Comparable<Node> {
        int node;
        int distance;

        Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 5, 1, 0},
            {2, 0, 0, 3, 0},
            {5, 0, 0, 3, 1},
            {1, 3, 3, 0, 5},
            {0, 0, 1, 5, 0}
        };

        int n = graph.length;
        int[] distance = new int[n];

        int start = 0; // 출발지 설정

        dijkstra(graph, distance, start);

        System.out.println("출발지로부터 각 노드까지의 최단 거리:");
        for (int i = 0; i < n; i++) {
            System.out.println("노드 " + i + ": " + distance[i]);
        }
    }
}

 

위 코드에서 distance 배열은 DP 배열로, 각 인덱스 i에 해당하는 값은 출발지에서 노드 i까지의 최단 거리를 저장한다.

 

초기값으로 INF로 채워놓고, 출발지까지의 거리를 0으로 설정한다. 다익스트라 알고리즘을 사용하여 인접한 노드들의 최단 거리를 갱신하며 목적지까지의 최단 거리를 구할 수 있다.

DP 배열을 활용하면 이전에 계산한 결과를 저장하여 중복 계산을 피하고 문제를 효율적으로 해결할 수 있고, 최단 경로 문제뿐만 아니라 다른 다이내믹 프로그래밍 문제에서도 DP 배열은 유용하게 사용된다.