[백준] 1753 최단경로

문제

https://www.acmicpc.net/problem/1753

고민

올게 왔다.. 바로 다익스트라

 

다익스트라는 선택된 곳에서 다른 노드들 까지의 거리다.

다른 길찾기 알고리즘 에서는 A에서부터 D까지 가는 방법 중 여러가지였다면

다익스트라는 A에서 출발할건데 다른 노드들까지 가는 방법의 비용을 산출하는 거다.

 

(이쯤되면 길찾기 알고리즘은 말만 조금씩 다를 뿐 푸는 방식이 같다는 느낌까지 듦)

 

문제는 간단하다. 주어진 시작점에서 다른 노드들간의 거리를 구하는 것

1. 우선순위 큐를 사용하여 시간복잡도를 줄이기

2. 거리가 가까우면 업데이트하기

 

위 두가지만 고민하면 된다.

 

나는 2번이 너무 헷갈렸다. 업데이트 하는 로직이 떠오르지 않아서 다른 사람 코드도 봤는데 이해가 힘들었다.

현재 노드까지 거리에다가 다음 노드까지 비용을 계산한다? 이게 쉽게 이해되지 않았다.

A -> B로 가는 비용이 3

B -> C로 가는 비용이 1이라 했을 때

 

거리 배열에 [ 0, 3, ?]이 담겨있다.

 

A에서 C로 간다면? B를 거쳐 C로 가야한다.

A에서 B까지 가는 최단 경로는 3이니까

B(A+B) + C를 더하면 A에서부터 C까지 가는 거리다.

 

이렇게 문제를 풀면 코드는 다음과 같다.

C# 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 다익스트라
{
    class Node
    {
        public int nextNode, cost;

        public Node(int nextNode, int cost)
        {
            this.nextNode = nextNode;
            this.cost = cost;
        }
    }

    internal class 최단경로
    {
        static int N; // 1부터 V까지 번호가 적혀있음
        static int E; // 간선
        static int S; // 시작점의 정점 번호
        static int INF = int.MaxValue;
        static List<Node>[] map;
        static int[] distance;
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            N = input[0];
            E = input[1];
            S = int.Parse(Console.ReadLine());

            map = new List<Node>[N+1];
            distance = new int[N+1];
            Array.Fill(distance, INF);

            for (int i = 1; i <= N; i++)
            {
                map[i] = new List<Node>();
            }

            for(int i = 0; i < E; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                int currentNode = input[0];
                int nextNode = input[1];
                int cost = input[2];

                map[currentNode].Add(new Node(nextNode, cost));
            }

            Dijkstra(S);

            for(int i = 1; i <= N; i++)
            {
                if (distance[i] >= int.MaxValue)
                {
                    Console.WriteLine("INF");
                }
                else
                {
                    Console.WriteLine(distance[i]);
                }
            }
        }

        private static void Dijkstra(int s)
        {
            PriorityQueue<Node, int> pq = new PriorityQueue<Node, int>();
            pq.Enqueue(new Node(s, 0), 0);
            distance[s] = 0; // 나에서 나까지 거리는 0임

            while(pq.Count > 0)
            {
                Node currentNode = pq.Dequeue(); //pq에서 하나 꺼내
                int currentIndex = currentNode.nextNode;
                int currentDist = currentNode.cost;

                if(currentDist > distance[currentIndex]) // 현재 비용이 현재 인덱스에 저장된 비용보다 크면 굳이 확일 할 필요 없으니 컨티뉴
                {
                    continue;
                }

                foreach(var node in map[currentIndex])
                {
                    int nextIndex = node.nextNode;
                    int nextDist = currentDist + node.cost; // 현재까지 거리 + 다음 노드까지 거리 더한게 다음 노드로 가는 길

                    if(nextDist < distance[nextIndex]) // 다음 비용 다음 인덱스에 저장된 비용보다 작으면 업데이트
                    {
                        distance[nextIndex] = nextDist;
                        pq.Enqueue(new Node(nextIndex, nextDist), nextDist); // 다음 인덱스와 다음 거리를 큐에 삽입
                    }
                }
            }

        }
    }
}

 

 

변수명을 너무 우당탕탕 마음대로 적은 거 같아서 다른 사람이 보기에 이해하기 힘들면 어쩌지 걱정된다.

다익스트라 반복문에서 갑자기 distance로 변경되어서 그렇지 cost와 distance는 같은 의미다!