[알고리즘 문제 풀기] 최단경로(1753)

1. 문제 풀이 아이디어

• 시작 정점에서 모든 정점까지의 최단 거리를 구하는 데이크스트라 알고리즘을 한 번만 실행하여 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
using System.Collections.Generic;

class PriorityQueue<T>
{
    private List<Tuple<T, int>> _heap = new List<Tuple<T, int>>();
    private void Swap(int i, int j)
    {
        var temp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = temp;
    }
    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parent = (index - 1) / 2;
            if (_heap[index].Item2 >= _heap[parent].Item2) break;
            Swap(index, parent);
            index = parent;
        }
    }
    private void HeapifyDown(int index)
    {
        int last = _heap.Count - 1;
        while (true)
        {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;
            if (left <= last && _heap[left].Item2 < _heap[smallest].Item2)
                smallest = left;
            if (right <= last && _heap[right].Item2 < _heap[smallest].Item2)
                smallest = right;
            if (smallest == index) break;
            Swap(index, smallest);
            index = smallest;
        }
    }
    public void Enqueue(T item, int priority)
    {
        _heap.Add(Tuple.Create(item, priority));
        HeapifyUp(_heap.Count - 1);
    }
    public T Dequeue()
    {
        var root = _heap[0].Item1;
        _heap[0] = _heap[_heap.Count - 1];
        _heap.RemoveAt(_heap.Count - 1);
        HeapifyDown(0);
        return root;
    }
    public int PeekPriority()
    {
        return _heap[0].Item2;
    }
    public int Count => _heap.Count;
}

class Program
{
    static void Main(string[] args)
    {
        StringBuilder sb = new StringBuilder("");

        using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
        using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
        {
            string[] split = sr.ReadLine().Split();
            int n = int.Parse(split[0]);
            int m = int.Parse(split[1]);
            int k = int.Parse(sr.ReadLine());
            Dictionary<int, int>[] dict = new Dictionary<int, int>[n + 1];
            for (int i = 1; i <= n; i++) dict[i] = new Dictionary<int, int>();
            for (int i = 0; i < m; i++)
            {
                split = sr.ReadLine().Split();
                int a = int.Parse(split[0]);
                int b = int.Parse(split[1]);
                int d = int.Parse(split[2]);
                if (dict[a].ContainsKey(b))
                {
                    if (dict[a][b] > d)
                    {
                        dict[a][b] = d;
                    }
                }
                else
                {
                    dict[a].Add(b, d);
                }
            }
            int[] result = Dijkstra(k);
            for (int i = 1; i <= n; i++)
            {
                sb.AppendLine(result[i] == int.MaxValue ? "INF" : result[i].ToString());
            }
            sw.Write(sb);

            int[] Dijkstra(int start)
            {
                var pq = new PriorityQueue<int>();
                var visited = new bool[n + 1];
                var minDist = new int[n + 1];

                for (int i = 1; i <= n; i++)
                    minDist[i] = int.MaxValue;

                minDist[start] = 0;
                pq.Enqueue(start, 0);

                while (pq.Count > 0)
                {
                    int cur = pq.Dequeue();
                    if (visited[cur]) continue;
                    visited[cur] = true;

                    foreach (var next in dict[cur])
                    {
                        int nextNode = next.Key;
                        int weight = next.Value;
                        int newDist = minDist[cur] + weight;

                        if (newDist < minDist[nextNode])
                        {
                            minDist[nextNode] = newDist;
                            pq.Enqueue(nextNode, newDist);
                        }
                    }
                }

                return minDist;
            }
        }
    }
}

3. 정리

• 입력에서 정점 수 n, 간선 수 m, 시작 정점 k를 받아온다.

• 인접 리스트로 간선 정보를 저장하며, 같은 간선이 여러 번 들어올 수 있으므로 더 짧은 거리만 유지한다.

• 데이크스트라 알고리즘을 시작 정점 k에서 한 번만 수행하여 모든 정점까지의 최단 거리를 구한다.

• 결과 배열을 순회하면서, int.MaxValue이면 도달 불가능한 경우이므로 "INF"를 출력하고, 아니라면 최단 거리를 출력한다.