개요
최근에 알고리즘 공부를 본격적으로 시작하면서 자바의 다양한 자료구조를 사용할 일이 많아졌습니다. 그 중에서도 많은 알고리즘 문제가 우선 순위 큐를 통해 조금 더 쉽게 접근이 가능하다는 사실을 알았습니다. 저 또한 여러 문제를 우선 순위 큐를 사용해 해결하고 있는데요 우선순위 큐가 무엇이고 어떻게 사용하는지 간략하게 설명해보고자 합니다.
PriorityQueue란?
자바에서 PriorityQueue는 우선순위 큐를 구현한 클래스입니다. 우선순위 큐는 요소들을 저장하고 관리하는 자료구조로, 각 요소는 우선순위라는 값을 가지고 있습니다. 우선순위 큐에서는 요소들이 우선순위에 따라 정렬되며, 가장 우선순위가 높은 요소가 항상 먼저 나오게 됩니다.
PriorityQueue는 내부적으로 힙(heap)이라는 자료구조를 사용하여 구현됩니다. 힙은 완전 이진트리(complete binary tree)를 기반으로 한 자료구조로서, 부모 노드와 자식 노드 간의 우선순위 관계를 유지합니다. 이를 통해 PriorityQueue는 삽입과 삭제 연산을 효율적으로 수행할 수 있습니다.
PriorityQueue 클래스의 주요 특징과 메서드는 다음과 같습니다.
-
요소 추가: add(E element), offer(E element)
주어진 요소를 우선순위 큐에 추가합니다.
요소는 우선순위에 따라 정렬됩니다. -
요소 제거: remove(), poll()
우선순위가 가장 높은 요소를 제거하고 반환합니다.
큐가 비어있는 경우 null을 반환합니다. -
요소 접근: element(), peek()
우선순위가 가장 높은 요소를 반환합니다.
큐가 비어있는 경우 null을 반환합니다. -
크기 정보: size(), isEmpty()
큐에 저장된 요소의 개수를 반환합니다.
큐가 비어있는지 여부를 확인합니다.
PriorityQueue는 기본적으로 자연 순서(natural order)에 따라 요소를 정렬합니다. 즉, 요소의 클래스가 Comparable 인터페이스를 구현하고 있다면, 해당 클래스의 compareTo() 메서드를 사용하여 요소의 우선순위를 결정합니다. 또한, 사용자 정의한 비교자(comparator)를 지정하여 요소의 우선순위를 커스터마이즈할 수도 있습니다.
어떤 상황에서 사용하는데?
백준의 아기 상어라는 문제가 있습니다. 물고기와 상어의 위치가 배열의 형태로 주어지고, 모든 물고기를 먹을 수 있는 최소 경로를 찾는 문제입니다. 여기서 문제는 다음과 같은 조건을 내새웠습니다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
이 모든 조건을 if-else로 하나씩 명세한다면 코드는 매우 복잡해질 것입니다. 하지만 우선순위 큐로 쉽게 해결할 수 있습니다. 코드를 통해 우선 순위를 커스터마이즈 하는 방법을 같이 알려드리겠습니다.
static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int compareDist = o1[2] - o2[2];
if (compareDist != 0) {
return compareDist;
}
int compareY = o1[0] - o2[0];
if (compareY != 0) {
return compareY;
}
return o1[1] - o2[1];
}
});Comparator 인터페이스와 compare 함수를 Override 함으로써 우선 순위를 재 설정할 수 있습니다.
위의 조건인 먹을 수 있는 물고기가 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.는 우선 순위를 거리가 짧은 물고기 좌표를 앞에 저장하는 로직을 구현함으로써 해결하였습니다.
여기서 compareDist!=0 이라는 조건문을 확인하실 수 있는데요, 이는 만약에 거리가 같다면 (즉, 거리의 차가 0이 되어 우선 순위를 판단할 수 없는 경우) 두 번째 조건으로 넘어갑니다.
두 번째 조건은 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다 인데요, 물고기의 Y좌표를 비교해서 더 높은 칸에 있는 물고기가 앞에 저장되야합니다.
이해가 안되는데요?
배열이 있다고 가정해봅시다.
int [][] board = new int [5][5];배열은 숫자가 낮을 수록 왼쪽 혹은 위쪽에 위치합니다.
가령 board[1][2] 가 있고 board[3][4]가 있다면 board[1][2]가 왼쪽 그리고 위쪽에 위치하고 있겠죠.
여기서 값을 int [] 형태로 전달하여 헷갈릴 수 있는데 [0], [1], [2] 에는 각각 세로, 가로, 거리가 저장되어 있습니다.
마지막 조건 또한 위에서 설명했던 내용과 유사합니다. compareDist, compareY가 모두 0이면 다음 우선순위를 설정하는 것이죠!
마무리
실제 예제를 통해 쉽게 설명하고자 했는데 이해가 잘 되었을지 모르겠습니다. 우선순위 큐를 사용한 여러 예제 또한 업로드 할 예정이니 참고하시면 좋을 것 같습니다. 꾸준히 좋은 글로 찾아뵙겠습니다. 감사합니다 :)
