[MEMO] Priority Queue의 우선순위 규칙에 관하여

우선순위 큐 (Priority Queue)

BOJ 16236 : 아기상어 를 해결하는 과정에서 다음과 같은 조건이 주어졌다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

여기서 내가 주목한 점은 마지막 조건이다. 일반적인 BFS문제에서는 우선순위를 두지 않지만 이 문제에서는 필요할 것 같았다.

따라서 pq의 성질을 이해할 필요가 있었으며 2차원 배열에서의 BFS를 다룰 예정이었기 때문에 distance정보와 location정보를 동시에 담는 pq 내부에서 우선순위를 어떻게 정하나 알아볼 필요가 있었다.

다음과 같은 코드를 작성하였다.

#include <iostream>
#include <queue>
using namespace std;
using pii = pair<int, int>; // {x, y}

int main(){
    priority_queue<pair<int, pii>> pq;
    // {distance, {location}}

    pq.push({1, {2,1}});
    cout << pq.top().first << pq.top().second.first << pq.top().second.second << "\n";
    
    pq.push({1, {3,1}});
    cout << pq.top().first << pq.top().second.first << pq.top().second.second << "\n";

    pq.push({1, {3,2}});
    cout << pq.top().first << pq.top().second.first << pq.top().second.second << "\n";

    return 0;
}

이렇게 진행하니 다음과 같은 결과값이 나왔다.

121
131
132

Summary

첫번째 인자로 들어가있는 distance값이 가장 우선되며
이후로는 location의 첫번째 인자인 x,
마지막으로 location의 두번째 인자인 y가 우선된다는 것을 알 수 있었다.