[백준][C#] 1753 최단경로 - 골드4

문제 보기

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

1753번: 최단경로

 

문제                           

 

입력                          

 

출력                          

 

 

시간 제한	메모리 제한
1 초	256 MB

 

 

풀이방법                 

막 다익스트라 문제를 포스팅하고 다음 문제를 풀었는데

또 괜찮은 다익스트라 문제를 발견해서 포스팅하기로 결정하였다.

https://mountain-noroo.tistory.com/36

[백준][C#] 1504 특정한 최단 경로 - 골드4

 

방금의 문제보다 훨씬 간단하지만 하나 달리 적용해야 할 점이 있는데,

정점의 최대 개수가 훨씬 많다는 것.

 

 

이전 문제에서는 인접행렬을 이용해 문제를 풀었으나

이번 문제에서는 인접리스트를 이용해 문제를 풀어야만한다.

 

 

인접 행렬과 인접 리스트에 대한 자세한 설명이 있는 블로그

https://sarah950716.tistory.com/12

[그래프] 인접 행렬과 인접 리스트

 

int[] Dijkstra(int start)
{
	bool[] visited = new bool[V + 1];
	Queue<(int v, int weight)> queue = new Queue<(int, int)>();
    queue.Enqueue((start, 0));
    visited[start] = true;

    int[] minWeights = new int[V + 1];
    for (int i = 1; i <= V; i++)
    {
    	minWeights[i] = int.MaxValue;
    }

    minWeights[start] = 0;

    while (queue.Count > 0)
    {
    	(int v, int weight) = queue.Dequeue();

		// 인접 행렬과 차이가 있는 부분
        // weights 인접 리스트는 List<(int v, int weight)> 형 배열이다.
        // 연결 된 정점과, 현재 정점에서 그 정점까지의 거리를 나타낸다.
        // List<(int v, int weight)>[] weights;
        // weights[v] 리스트의 요소 개수 만큼 순회한다.
        int count = weights[v].Count;
        for (int i = 0; i < count; i++)
        {
        	// minWeights 갱신
        	minWeights[weights[v][i].vertex] 
            = Math.Min(weight + weights[v][i].weight, minWeights[weights[v][i].vertex]);
        }

        int index = 0;
        int min = int.MaxValue;
        for (int i = 1; i <= V; i++)
		{
			if (!visited[i])
			{
				if (min > minWeights[i])
				{
					min = minWeights[i];
					index = i;
				}
			}
		}

		if (min == int.MaxValue)
			break;

		queue.Enqueue((index, min));
		visited[index] = true;
		}

	return minWeights;
}

 

주석이 달리지 않은 부분은 위에 있는 1504번 문제 포스팅을 참고 바란다.

 

시작 정점으로부터 모든 정점까지의 거리이기 때문에 minWeights 배열을 순회하며 값을 출력하면 된다.

 

int[] minWeights = Dijkstra(startVertex);
for(int i = 1; i <= V; i++)
{
	if (minWeights[i] >= int.MaxValue)
    	print.WriteLine("INF");
    else
    	print.WriteLine(minWeights[i]);
}

 

 

 

전체 코드

using System;
using System.Collections.Generic;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();
            int V = int.Parse(inputs[0]);
            int E = int.Parse(inputs[1]);

            List<(int vertex, int weight)>[] weights = new List<(int vertex, int weight)>[V + 1];
            for(int i = 0; i < V + 1; i++)
            {
                weights[i] = new List<(int, int)>();
            }

            int startVertex = int.Parse(reader.ReadLine());
            for (int i = 0; i < E; i++)
            {
                inputs = reader.ReadLine().Split();
                weights[int.Parse(inputs[0])].Add((int.Parse(inputs[1]), int.Parse(inputs[2])));
            }

            int[] minWeights = Dijkstra(startVertex);
            for(int i = 1; i <= V; i++)
            {
                if (minWeights[i] >= int.MaxValue)
                    print.WriteLine("INF");
                else
                    print.WriteLine(minWeights[i]);
            }

            int[] Dijkstra(int start)
            {
                bool[] visited = new bool[V + 1];
                Queue<(int v, int weight)> queue = new Queue<(int, int)>();
                queue.Enqueue((start, 0));
                visited[start] = true;

                int[] minWeights = new int[V + 1];
                for (int i = 1; i <= V; i++)
                {
                    minWeights[i] = int.MaxValue;
                }

                minWeights[start] = 0;

                while (queue.Count > 0)
                {
                    (int v, int weight) = queue.Dequeue();

                    int count = weights[v].Count;
                    for (int i = 0; i < count; i++)
                    {
                        minWeights[weights[v][i].vertex] = Math.Min(weight + weights[v][i].weight, minWeights[weights[v][i].vertex]);
                    }

                    int index = 0;
                    int min = int.MaxValue;
                    for (int i = 1; i <= V; i++)
                    {
                        if (!visited[i])
                        {
                            if (min > minWeights[i])
                            {
                                min = minWeights[i];
                                index = i;
                            }
                        }
                    }

                    if (min == int.MaxValue)
                        break;

                    queue.Enqueue((index, min));
                    visited[index] = true;
                }

                return minWeights;
            }

            reader.Close();
            print.Close();
        }
    }
}