[priority queue] 우선순위 큐 구조체 오름차순 정렬, custom sort

priority queue의 custom sort를 찾아보게된 이유는 다익스트라 알고리즘 때문이다.

하얀색 박스를 보면 (-) 부호를 붙이는 모습을 볼 수 있다.

이는 구현의 편의를 위해 priority_queue를 사용하는데, 알고리즘 흐름상 우리는 오름차순으로 값을 얻기를 원하지만, priority queue는 자동으로 내림차순으로 출력되기 때문에(큰 값이 앞에 오기 때문에) 부호를 바꾸어가며 사용하는 것이다.

이를 보며 sort() 함수에서 세 번째 인자로 custom compare 함수를 만들어 사용하듯 priority queue도 custom sort가 가능하지 않을까 하여 찾아보았다.

결론부터 말하자면 찾아본 방법 중 여러 방법이 있지만, 그 중 두 가지 정도 방법을 사용할 것 같다. 사용자가 선언한 임의의 구조체 T를 자료형으로 가진다고 가정하자.

1. operator() 오버로딩
   • 구조체로 해당 부분을 감싼 후 operator() 연산자를 오버로딩 하는 방식
   • priority_queue 선언은 priority_queue <T, vector<T>, compare> pq; 다음과 같은 syntax를 갖는다.
2. operator< 오버로딩
   • operator<(const T& a, const T& b) 혹은 operator<(T a, T b) 
   • priority_queue 선언은 priority_queue <T> pq; 다음과 같은 syntax를 같는다.

구현 코드

#include <iostream>
#include <queue>
using namespace std;

struct point{
	int x;
	int y;
	int z;
};
// z -> y -> x 의 우선순위를 가지며, 오름차순으로 정렬되도록 하는 priority_queue를 선언
// 1. cmp 구조체로 감싼 후 operator() 연산자 오버로딩
struct cmp {
	bool operator()(point a, point b) {
		if (a.z == b.z) {
			if (a.y == b.y) {
				return a.x > b.x;
			}
			return a.y > b.y;
		}
		return a.z > b.z;
	}
};

// 2. operator< 연산자 오버로딩
bool operator<(point a, point b) {
	if (a.z == b.z) {
		if (a.y == b.y) {
			return a.x > b.x;
		}
		return a.y > b.y;
	}
	return a.z > b.z;
}

// 3. 마찬가지로 operator< 연산자 오버로딩, 인자를 레퍼런스로 전달받는 차이 존재
bool operator<(const point& a, const point& b) {
	if (a.z == b.z) {
		if (a.y == b.y) {
			return a.x > b.x;
		}
		return a.y > b.y;
	}
	return a.z > b.z;
}

int main() {
	// 1번 코드를 실행해보고 싶으면 아래 선언의 주석을 풀고, 기존 pq선언을 주석처리하고 사용
	// priority_queue<point, vector<point>, cmp> pq;
	priority_queue <point> pq;
	int t;
	cout << "입력할 정수의 개수를 입력하세요 : ";
	cin >> t;

	cout << "priority_queue에 입력할 임의의 수를 엔터를 기준으로 세 개씩 입력하세요\n";
	for (int i = 0; i < t; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		pq.push({ x, y, z });
	}
	for (int i = 0; i < t; i++) {
		point p = pq.top();
		pq.pop();
		cout << "(" << p.x << ", " << p.y << ", " << p.z << ")\n";
	}
}

operator(), operator< 연산자 오버로딩에 따른 코드를 실제로 확인해보기 위해 위와 같이 코드를 작성해보았으며, 주석만 적절히 해주며 실제로 테스트해보면 세 가지 방법 모두 정상적으로 동작하는 것을 확인할 수 있다. 이제 왜 저렇게 되는지 이유를 살펴보자

 

1. operator() 오버로딩이 가능한 이유

https://en.cppreference.com/w/cpp/container/priority_queue

해당 링크에 들어가 확인해보면 위 이미지와 같은 syntax가 priority_queue 선언의 기본 구조라고 말하고 있다.

// priority_queue의 기본 선언형은 다음과 같은 syntax를 갖는다.
priority_queue <int, vector<int>, less<int>>pq;
priority_queue <int> pq;

priority_queue <int, vector<int>, greater<int>>pq;

해당 문서를 통해 확인해보면 위와 같은 코드에서 1번, 2번 코드는 동일한 의미를 가지며, 3번 코드의 경우 priority_queue가 작은 값을 먼저 출력하도록 하고 싶을 때 greate<int>를 이용하면 된다는 것을 알 수 있다.

때문에 위 코드에서 int 를 본인이 사용하고자 하는 구조체나 클래스로 대체하고, greater<>, less<> 를 적절히 커스텀해주면 원소를 원하는 방식으로 정렬이 가능할 것 같다. 이제 greater<>와 less<> 가 어떤 구조를 가지는지 살펴보고, 어떻게 커스텀하면 될지 알아보자

https://cplusplus.com/reference/functional/less/

해당 링크에 들어가면 less가 어떻게 동작하도록 정의되어 있는지 나와있다.

여기서 operator() 연산자를 오버로딩하도록 bool 함수로 구현 후, struct로 감싸는 이유를 알 수 있다. less 함수에서 operator() 가 왜 저렇게 비교를 할 수 있는지, 어떻게 동작이 이루어지는 것인지는 잘 모르지만 위 형태를 그대로 가져와 우리가 원하는 모양으로 코드를 작성하면 될 것 같다.

struct point{
	int x;
	int y;
	int z;
};

struct cmp {
    bool operator()(point a, point b) {
	    if (a.z == b.z) {
			if (a.y == b.y) {
				return a.x > b.x;
			}
			return a.y > b.y;
		}
		return a.z > b.z;
	}
};

priority_queue<point, vector<point>, cmp> pq;

때문에 똑같이 operator() 연산자를 원하는대로 오버로딩, 이를 구조체로 감싸줌으로써 custom sort가 가능한 것이다.

 

2. operator< 오버로딩이 가능한 이유

https://stackoverflow.com/questions/684669/why-does-operator-need-to-be-overloaded-when-implementing-class-based-priority

https://stackoverflow.com/questions/19535644/how-to-use-the-priority-queue-stl-for-objects

위 두 개의 질문에 대한 답변으로부터 유사한 답변들을 얻을 수 있었다. 답변들의 공통점을 대략 요약하자면 

STL container들은 원소를 정렬하기위해 default로 operator< 연산자를 사용한다. 때문에 operator< 연산자를 오버로딩함으로써 원하는 정렬 결과를 얻을 수 있다.때문에 다음과 같은 코드로 custom sort가 가능하다.

 

struct point{
	int x;
	int y;
	int z;
};

bool operator<(point a, point b) {
	if (a.z == b.z) {
		if (a.y == b.y) {
			return a.x > b.x;
		}
		return a.y > b.y;
	}
	return a.z > b.z;
}

bool operator<(const point& a, const point& b) {
	if (a.z == b.z) {
		if (a.y == b.y) {
			return a.x > b.x;
		}
		return a.y > b.y;
	}
	return a.z > b.z;
}

priority_queue <point> pq;

조금 더 찾아보고 구조적으로 operator(), operator< 를 오버로딩 하는 것에는 어떠한 차이가 있는지 알고 싶었지만, 그러기 위해서는 시간을 조금 더 써야할 것 같다...누군가 아는 분이 계시다면 댓글로 꼭 훈수 부탁드립니다...

 

3. operator<(const point& a, const point& b) / operator<(point a, point b) 의 차이

https://stackoverflow.com/questions/7912595/initialization-for-stl-priority-queue

위 링크에서 두 번째로 달린 답변을 읽다가 위와 같은 글을 발견하였다. 결국 자세한 구조적인 이유는 모르겠지만, reference로 인자를 넘기기 원한다면 const가 꼭 있어야하고, 단순히 call by value로 인자를 넘길 경우는 const가 없어도 에러 없이 코드가 동작하긴 한다.

 

글을 다 쓴 후에도 명확히 상관관계를 밝히지 못한 내용들이 많이 눈에 보여 조금 더 찾아보고 싶지만, 잠시 미루어두는 것으로 하고 일단은 priority_queue를 사용할 때 어떻게 연산자 오버로딩을 하면 되는지 정확한 문법을 알게된 것에 만족한다.

잘못된 내용이 충분히 있을 수 있다고 생각하므로...잘못 적힌 내용이 있다면 댓글을 통한 지적 언제나 환영합니다...

공부하는 데에 많이 참고가 된 블로그들

https://huilife.tistory.com/entry/C-Priority-Queue%EC%9D%98-custom-sort
https://niklasjang.github.io/algorithm/STL-priority-queue/
https://koosaga.com/9