왜 필요할까?
C#에서 우선순위큐(Prirority_Queue)는 NET 7에 새로 생겼다.
이게 문제가 되는 이유는
대표적인 알고리즘 풀이 사이트(백준, 프로그래머스)가. NET 7 하위 버전이다.
즉, C#으로 알고리즘을 풀 때 우선순위 큐를 사용할 수 없다는 소리다.
SortedSet
SortedSet에 대해 자세히 다루는 포스팅은 아니기 때문에
우선순위 큐 구현에 필요한 핵심만 말하겠다.
SortedSet은 내부의 요소가 자동적으로 정렬된다.
이때 중복 요소는 허용되지 않는다.
원시타입(string, int) 같은 경우,
정렬 기준을 만들지 않으면 자동으로 오름차순으로 정렬되지만
컬렉션, 배열 등은 무조건
IComparable 혹은 IComparer를 통해 정렬 기준을 만들어야 한다.
SortedSet을 사용할 수 있는 결정적인 이유는
원소의 추가, 검색, 삭제의 시간복잡도가 O(logN)밖에 되지 않기 때문이다.
우선순위 큐 구현
public class Program
{
// 정렬 기준
public class Mycompare : IComparer<string>
{
// 문자열의 길이에 따라 오름차순
public int Compare(string x, string y)
{
return x.Length - y.Length;
}
}
public static void Main(String[] args)
{
// 우선순위 큐 선언
SortedSet<string> priority_queue = new SortedSet<string>(new Mycompare());
priority_queue.Add("ABC"); // pq.Push
priority_queue.Add("ABCDDF");
priority_queue.Add("AB");
priority_queue.Add("CDDD");
priority_queue.Add("C");
// 큐 안의 원소가 몇개있는지 확인
while (priority_queue.Count > 0)
{
string item = priority_queue.First(); // peek
priority_queue.Remove(item); // pop
Console.WriteLine(item);
}
}
}
주석은 기존에 있는 우선순위 큐의 기능과의 대응을 적어놨다.
Push ↔ Add
First() ↔ Peek
Remove ↔ Pop
Count ↔ Size
출력 결과 길이가 제일 작은 C부터
길이순으로 큐에서 빠지는 것을 확인할 수 있다.
응용 - 다익스트라 알고리즘
이제 이를 이용하여 우선순위큐를 대표적으로
이용하는 다익스트라 알고리즘을 구현해 보자.
대충 이런 식의 단방향 그래프가 존재한다고 하자.
빨간색은 한 노드에서 한 노드로 가는 비용(가중치)이다.
using System;
using System.Collections.Generic;
namespace Algorithm
{
public class Program
{
public class Mycompare : IComparer<List<int>>
{
// 비용 기준으로 오름차순
public int Compare(List<int> x, List<int> y)
{
if (x[0] == y[0]) return x[1] - y[1];
return x[0] - y[0];
}
}
public static int[,] dist = new int[20, 20]; //[시작노드, 도착노드]
public static List<List<int>>[] node = new List<List<int>>[20]; // 노드 정보
// 다익스트라 알고리즘
public static void Dijkstra(int sx)
{
SortedSet<List<int>> pq = new SortedSet<List<int>>(new Mycompare());
dist[sx,sx] = 0;
pq.Add(new List<int>() { 0, sx });
while (pq.Count > 0)
{
List<int> cnt = pq.First();
pq.Remove(cnt);
int x = cnt[1];
int cost = cnt[0];
if (dist[sx, x] < cost) continue;
for (int i = 0; i < node[x].Count; i++)
{
int next = node[x][i][0];
int nCost = node[x][i][1] + cost;
if (dist[sx,next] > nCost)
{
dist[sx, next] = nCost;
pq.Add(new List<int>() { nCost, next });
}
}
}
}
public static void Main(String[] args)
{
//초기화
for (int i = 0; i < 20; i++) node[i] = new List<List<int>>();
// dist 배열 큰 값으로 맞춰줌
for(int i = 0; i < 20; i++)
for (int j = 0; j < 20; j++) dist[i, j] = 9999999;
// 노드 정보 담기
node[0].Add(new List<int>(){3,4});
node[1].Add(new List<int>(){0,3});
node[1].Add(new List<int>(){2,1});
node[1].Add(new List<int>(){3,3});
node[2].Add(new List<int>(){0,2});
node[2].Add(new List<int>(){3,1});
node[3].Add(new List<int>(){2,3});
for(int i = 0; i <= 3; i++) Dijkstra(i);
for (int i = 0; i <= 3; i++)
{
for (int j = 0; j <= 3; j++)
{
if (i == j) continue;
Console.WriteLine($"{i}번 노드에서 {j}번 노드로 갈 때의 최소 비용 = {dist[i,j]}");
}
}
}
}
}
정상적으로 출력이 나오는 것을 확인할 수 있다.
여기서 999999는 해당 노드에서 노드로 갈 수 없음을 의미한다.
이상으로 포스팅을 마치겠다.