우선순위 큐(Priority Queue) - 자바(JAVA)

우선순위 큐(Priority Queue)는 개발자가 자주 활용하는 자료구조 중 하나입니다. 이번에는 우선순위 큐에 대해 자세히 알아보고, 실제로 어떻게 사용되는지 예시 코드를 통해 살펴보겠습니다.

우선순위 큐는 요소들을 우선순위에 따라 정렬하여 저장하는 자료구조입니다. 일반적인 큐와 달리 요소들이 저장될 때 우선순위에 따라 정렬되므로, 가장 우선순위가 높은 요소에 먼저 접근할 수 있습니다. 우선순위는 개발자가 지정한 기준에 따라 결정됩니다.

예를 들어, 다익스트라 알고리즘에서 최단 경로를 찾는 과정에서 우선순위 큐를 사용할 수 있습니다. 출발지에서 각 노드까지의 최단 거리를 계산할 때, 우선순위 큐를 활용하여 현재까지의 최단 거리를 기준으로 노드를 선택하고 처리할 수 있습니다.

아래는 우선순위 큐를 활용한 최단 경로 문제의 예시 코드입니다.

 

import java.util.PriorityQueue;

public class Dijkstra {
    public static void main(String[] args) {
        // 그래프 초기화
        int[][] graph = {
            {0, 2, 5, 1, Integer.MAX_VALUE},
            {2, 0, 3, 2, Integer.MAX_VALUE},
            {5, 3, 0, 3, 1},
            {1, 2, 3, 0, 1},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 1, 1, 0}
        };
        
        int startNode = 0; // 출발 노드
        
        int[] distances = new int[graph.length]; // 최단 거리를 저장할 배열
        boolean[] visited = new boolean[graph.length]; // 방문 여부를 저장할 배열
        
        PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 생성
        
        // 출발 노드 초기화
        distances[startNode] = 0;
        pq.offer(new Node(startNode, 0));
        
        while (!pq.isEmpty()) {
            Node currentNode = pq.poll(); // 우선순위 큐에서 가장 우선순위가 높은 노드 선택
            
            int current = currentNode.node;
            
            if (visited[current]) {
                continue;
            }
            
            visited[current] = true;
            
            // 현재 노드와 연결된 인접 노드들을 탐색하여 최단 거리 업데이트
            for (int i = 0; i < graph[current].length; i++) {
                if (graph[current][i] != Integer.MAX_VALUE) {
                    int distance = distances[current] + graph[current][i];
                    
                    if (distance < distances[i]) {
                        distances[i] = distance;
                        pq.offer(new Node(i, distance));
                    }
                }
            }
        }
        
        // 결과 출력
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Node " + i + ": " + distances[i]);
        }
    }
    
    // 우선순위 큐에 저장할 노드 클래스
    static class Node implements Comparable<Node> {
        int node;
        int distance;
        
        public Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }
        
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
}

그래프 초기화

---

2차원 배열 'graph'를 사용하여 그래프를 표현합니다.
각 노드 간의 거리 정보를 포함하며, 'Integer.MAX_VALUE'는 무한대를 의미합니다.
출발 노드를 0으로 설정합니다.

 

최단 거리를 저장할 배열 및 방문 여부를 저장할 배열 초기화

---

'distances' 배열은 출발 노드로부터의 최단 거리를 저장합니다.
'visited' 배열은 각 노드의 방문 여부를 저장합니다.

우선순위 큐 초기화

---

'PriorityQueue<Node>'를 사용하여 우선순위 큐를 생성합니다.
'Node '클래스는 노드의 번호와 해당 노드까지의 거리를 저장합니다.
출발 노드를 초기화하고 우선순위 큐에 추가합니다.

 

다익스트라 알고리즘 수행

---

우선순위 큐가 비어있을 때까지 반복합니다.
우선순위 큐에서 가장 우선순위가 높은 노드를 선택합니다.
선택한 노드가 이미 방문한 노드라면 건너뜁니다.
선택한 노드를 방문 처리하고, 해당 노드와 연결된 인접 노드들을 탐색합니다.
현재까지의 최단 거리와 인접 노드와의 거리를 비교하여 최단 거리를 업데이트하고, 우선순위 큐에 추가합니다.

결과 출력

---

최단 거리 배열인 'distances'를 출력하여 각 노드까지의 최단 거리를 확인합니다.

이렇게 작성된 코드를 실행하면 다익스트라 알고리즘을 통해 출발 노드로부터 각 노드까지의 최단 거리가 계산되고 출력됩니다. 이를 통해 우선순위 큐가 최단 경로 문제를 효과적으로 해결하는 데 어떻게 활용되는지 알 수 있습니다.