[1916] - 최소비용 구하기

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

1916번: 최소비용 구하기

접근 방법

아주 간단한 다익스트라 문제였다. 입력받은 간선의 정보로 그래프를 그리고 다익스트라를 구현하여 가야하는 곳의 최소비용을 구하였다.

 

문제 풀이

• 입력받은 노선들을 리스트 배열로 (다음 지점, 가중치) 그래프를 만들기
• 탐색확인용 visited, 탐색 가중치를 넣을 distance 배열을 생성 -> distance배열의 초기값에는 버스의 개수*최대가중치값을 넣어줌
• 우선순위 큐로 다익스트라를 구현하여, 현재 dequeue 된 지점이 탐색하지 않았을 경우 그 점에 연결된 노드 들을 탐색하며 가중치를 비교 -> 작은것을 세트 후, 우선순위 큐에 다시 넣어주기
• 탐색이 끝나고, distance 가야할 곳의 인덱스 값 출력

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

namespace Baekjoon.Gold
{
    class _1916
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());
            List<(int, int)>[] graph = new List<(int, int)>[n+1];
            for (int i = 1; i <= n; i++)
                graph[i] = new List<(int, int)>();

            for(int i = 0; i<m; i++)
            {
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[arr[0]].Add((arr[1], arr[2]));
            }

            //시작, 종점
            int[] togo = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            bool[] visited = new bool[n + 1]; //탐색했는지
            int[] distance = Enumerable.Repeat(100000000, n + 1).ToArray(); //가중치
            PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); //(다음탐색점, 가중치)
            pq.Enqueue(togo[0], 0);
            distance[togo[0]] = 0;

            //다익스트라
            while(pq.Count > 0)
            {
                int point = pq.Dequeue();
                if (!visited[point])
                {
                    visited[point] = true;

                    foreach((int, int) next in graph[point])
                    {
                        distance[next.Item1] = Math.Min(distance[next.Item1], next.Item2 + distance[point]);
                        pq.Enqueue(next.Item1, distance[next.Item1]);
                    }
                }
            }

            Console.WriteLine(distance[togo[1]]);
        }
    }
}