우선순위 큐(최대힙, 최소힙), 다익스트라 알고리즘

 

1. 최소 힙, 최대 힙 (우선 순위 큐)

우선순위 큐 : 들어온 순서와 상관없이 정해진 기준에 따라 값이 먼저 나간다.

1-1. 사용법

• 최대 힙 - priority_queue<int> pq;
• 최소 힙 - priority_queue<int, vector<int>, greater<int>> pq;
• 맨 앞 - pq.top()

1-2. 사용 예시

1. 최대값 또는 최소값의 빠른 접근 및 삭제가 필요한 경우
   • 예를 들어, 데이터 스트림에서 현재까지 입력된 값 중 최대값 또는 최소값을 실시간으로 추적해야 할 때 유용합니다.
   • 예시: 주어진 데이터에서 k번째로 큰 요소를 찾아야 하는 경우.
2. 동적으로 데이터의 정렬이 필요한 경우
   • 리스트나 배열에 요소를 삽입하면서 정렬된 상태를 유지해야 하는 경우에 우선순위 큐가 유리합니다.
   • 예시: 정렬된 데이터 스트림에서 새로운 데이터가 추가될 때마다 정렬을 유지하면서 추가해야 할 때.
3. 이벤트 처리 시스템에서 우선순위가 있는 작업을 관리할 때
   • 예를 들어, 다양한 우선순위를 가진 작업들이 입력되었을 때, 우선순위에 따라 작업을 처리해야 할 때 사용됩니다.
   • 예시: 다익스트라(Dijkstra) 알고리즘에서 최단 경로를 찾기 위해 가장 작은 가중치를 가진 노드를 우선적으로 처리해야 할 때.
4. 그리디 알고리즘에서 우선순위가 높은 요소를 반복적으로 선택해야 하는 경우
   • 예를 들어, 허프만 코딩(Huffman Coding) 알고리즘에서는 가장 빈도가 낮은 두 요소를 반복적으로 합쳐 나가야 합니다.
   • 예시: 다양한 작업들을 처리하는데 작업의 중요도나 비용이 다를 때, 비용이 가장 낮은 작업부터 처리해야 하는 경우.

2. 다익스트라

2-1. 다익스트라 이론

• 간단하게 생각하면 다익스트라는 BFS 확장의 버전으로, 가중치가 추가된 BFS로 생각하자
• 가중치가 0이 아닌 정수이며, 최단 거리를 구해야 할 때 사용한다.
• 만약 음수 값의 가중치가 있다면 벨만-포드 알고리즘을 사용해야 한다.
• 다익스트라 목적 : 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 과정
  • 이때, 간선 or 가중치가 음수가 아님
• 다양한 문제에서 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 문제가 아닌, 여러 개의 정점에서 모든 정점까지의 거리 중 최대 or 최소 값을 구해야 할 때도, 만약 n의 크기가 크다면 다익스트라 x n번을 통해 답을 구해야 한다.

기본 이론

1. 최단 거리를 저장할 배열 만들기
2. 시작점에서 각 정점까지의 최단 거리 저장
3. 시작점의 거리를 0으로 설정
4. 최단 거리인 정점을 방문, 큐 pop, 주변 정점의 최단 거리 갱신
5. 4번을 n번을 반복하여 모든 정점을 방문하며 최단 거리 갱신
6. 시작점에서 모든 정점까지의 최단 거리를 저장한 배열이 완성

정리

• 다익스트라는 한 점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
• N개의 여러 정점에서 모든 정점까지의 거리 중 최대 OR 최소 값을 구해야 한다면?
  • N개의 정점을 반복문을 통해 하나의 정점으로
  • 그 후, 정해진 정점에서 모든 정점까지의 거리를 구함
  • 문제에서 원하는 값을 구함
  • N번의 다익스트라 후 문제에서 원하는 답을 구함

2-2. 다익스트라 구현

기본 이론 구현

#define MAX 10010
#define INF 2e9

vector<pair<int, int>> v[MAX] // pair<가중치, 노드 번호> v[MAX]
int dist[MAX]; // INF로 초기화 해줘야 함
bool visited[MAX];

int main() {
	int idx;
	int mn;
	
	// 입력
	...
	//
	
	dist[i] = 0;
	for(int i=0; i<n; i++) { // n번 반복
		idx = -1;
		mn = INF; // 모든 거리를 최대로 초기화 해야 함
		for(int j=1; j<=n; j++){
			if(!visited[j] && mn > dist[j]) { // 방문 안한 정점 중 가장 거리가 가까운 곳
				mn = dist[j];
				idx = j;
				}
		}
		
		visited[idx] = true; // 방문 처리
		for(int j=0; j<v[idx].size(); j++) {
			dist[v[idx][j].first] = min(dist[v[idx][j].first], dist[idx] + v[idx][j].second);
			}
		}
}	

• 하지만 위의 구현 사항은 기본적으로 시간 복잡도가 O(n^2)가 나오기 때문에 n이 10만이 넘어가면 최적화가 반드시 필요하다.
• 최적화를 위해 위의 “방문하지 않은 정점 중 가장 가까운 정점”을 찾는 로직을 우선순위 큐를 활용해 간단하게 바꿀 수 있다.

2-3. 최적화된 다익스트라

최적화 다익스트라 구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 10010
#define INF 2e9

int n, m;
vector<pair<int, int>> v[MAX] // pair<가중치, 노드 번호> v[MAX]
// 우선 순위 큐 사용 - 최소 힙으로 구성되어 가중치가 작은 노드가 먼저 나옴
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int dist[MAX]; // INF로 초기화 해줘야 함
bool visited[MAX];

int main() {
	int a, b, c, mn, cur, start;
	// n개의 정점 m개의 연결
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		// 만약 양방향 그래프라면
		v[b].push_back({a, c});
	}
	
	// 최단 거리 배열 초기화
	for(int i=1; i<=n; i++)
		dist[i] = INF;
	
	dist[start] = 0;
	pq.push({0, start});
	
	while(!pq.empty()){
		// 현재 가장 가까운 정점
		int cur = pq.top().second;
		// 시작점부터 현재 정점까지의 최단 거리일 수 있는 값
		int cost = pq.top().first;
		pq.pop();
		
		// 현재 정점의 최단거리라고 생각한 값(cost)이 실제 최단거리가 아니라면 넘기기
		if(dist[cur] != cost)
			continue;
		
		// 현재 정점과 연결된 정점 모두 탐색
		for(int i=0; i<v[cur].size(); i++)
		{
				// 현재 정점과 연결된 정점
				int nxt = v[cur][i].first;
				int nxt_cost = v[cur][i].second;
				
				if(dist[nxt] > cost + nxt_cost)
				{
					dist[nxt] = cost + nxt_cost;
					pq.push({dist[nxt], nxt});
				}
		}
	}
}