백준 C# 1916 최소비용 구하기

문제 

A 에서 B 로 향할 때, 최소간선의 비용을 사용한 모든 경로의 가중치 합을 구해라

조건

가중치는 10만 이하
노드는 10만개 이하

겪었던 문제

가중치가 10만 이하, 노드가 10만 이하이면 최소 가중치의 값이 10억이 될 수  있다.

그렇기에, 최소값을 비교하기 위한 초기값을 Inf로 10억을 할당해서 비교해야 된다.

 

해결

다익스트라의 알고리즘을 활용하여 탐색하는 방법을 적용

추가적인 방법은 가장 작은 가중치의 노드를 찾는 방법에서 정렬된 Queue를 사용하는 방식을 사용하면 더욱 간결해진다.

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

namespace consoleapp1
{
    internal class E1916_최소비용구하기
    {
        const int INF = 0x3f3f3f3f;
        static void Main(string[] args)
        {
            string[] input(StreamReader s) => s.ReadLine().Split();

            using(StreamReader sr = new StreamReader(Console.OpenStandardInput()))
            {
                int city = int.Parse(input(sr)[0]);
                int bus = int.Parse(input(sr)[0]);

                int[,] cost = new int[city, city];

                bool[] visit = new bool[city];
                int[] minCost = new int[city];

                //배열 초기화
                for(int i = 0; i < city; i++)
                {
                    for(int j = 0; j < city; j++)
                    {
                        if (i != j) cost[i, j] = INF;
                    }
                }

                //비용 받기
                for (int i = 0;i< bus; i++)
                {
                    int[] temp = Array.ConvertAll(input(sr), int.Parse);
                    if (temp[0] == temp[1]) continue;
                    if(cost[temp[0] - 1, temp[1] - 1] > temp[2])
                        cost[temp[0] - 1, temp[1] - 1] = temp[2];
                }

                //현재 위치와 목표지점 입력 받기
                int[] goal = Array.ConvertAll(input(sr), int.Parse);
                goal[0] -= 1; goal[1] -= 1;
                for(int i= 0;i< city; i++) { minCost[i] = cost[goal[0],i]; }
                visit[goal[0]] = true;

                //작은 가중치 탐색
                for(int i = 0; i< city; i++)
                {
                    //최솟값 찾기
                    int minIndex = GetMinIndex(visit, minCost);

                    //탐색 가능한 경우가 없는 경우 제거
                    if (minIndex < 0) break;
                    visit[minIndex] = true;
                    for(int j = 0 ; j < city; j++)
                    {
                    //방문한 노드에서 다음 노드까지의 가중치가 이전 가중치보다 작다면 등록
                        if ((minCost[j] > minCost[minIndex] + cost[minIndex, j]) && !visit[j])
                        {
                            minCost[j] = minCost[minIndex] + cost[minIndex, j];
                        }
                    }
                }

                Console.WriteLine(minCost[goal[1]]);
            }
        }

        //현재 미방문 노드중 가장 작은 노드를 불러옵니다.
        static int GetMinIndex(bool[] visit, int[] minCost)
        {
            int index = -1;
            int min = INF;
            for(int i =0; i<visit.Length; i++)
            {
                if (!visit[i] && (minCost[i] < min))
                {
                    min = minCost[i];
                    index = i;
                }
            }
            return index;
        }
    }
}