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

문제 보기

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

1504번: 특정한 최단 경로

 

문제                           

 

입력                          

 

출력                          

 

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

 

풀이방법                 

간선에 가중치가 있는 것으로 보아하니 다익스트라(데이크스트라)를 그대로 적용하면 되는 문제.

혹시 다익스트라 알고리즘에 대해 모르고 있다면, 그래프 탐색에 친숙할 경우 어려운 개념은 아니기 때문에 관련 글을 찾아보고 오면 될 것 같다.

아래 링크는 구글에 검색하면 최상단에 나오는 블로그

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

그럼 우선 다익스트라 알고리즘을 통해 최소값을 구하는 과정부터 살펴보자.

// 출발 정점과 도착 정점을 받아온다.
int Dijkstra(int start, int end)
{
	// 같은 정점을 여러 번 방문하지 않도록
    // 문제에 "세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다."라는 
    // 말이 써져있어 헷갈릴 수 있는데 차후 설명하겠다.
	bool[] visited = new bool[N + 1];
    // 정점 v와 거리 튜플을 담는 queue 생성
	Queue<(int v, int distance)> queue = new Queue<(int, int)>();
    // 시작 정점과 거리 (시작 정점에서 시작 정점까지의 거리는 0)
    queue.Enqueue((start, 0));
    // 시작 정점을 방문.
    visited[start] = true;
	
    // 시작 정점에서 모든 정점까지의 최소 거리를 저장하는 배열이다.
    int[] minDistance = new int[N + 1];
    // 모두 int.MaxValue로 초기화.
    for (int i = 1; i <= N; i++)
    {
    	minDistance[i] = int.MaxValue;
    }
	while (queue.Count > 0)
    {
    	(int v, int distance) = queue.Dequeue();

        for (int i = 1; i <= N; i++)
        {
        	// distances 배열은 한 정점에서 다른 정점까지의 거리를 담은 2차원 배열이다.
            // 이 거리가 (초기 값인) 0이 아니라면.
            // "임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다."라 써져있기 때문에 생략 가능
        	if (distances[v, i] != 0)
            	// minDistance의 값을 업데이트 해준다.
        		minDistance[i] = Math.Min(distance + distances[v, i], minDistance[i]);
        }

		// 아래는 다음 방문할 정점을 정하는 코드다.
        // 다익스트라 알고리즘에서는 아직 방문하지 않은 정점 중
        // 거리가 제일 짧은 정점을 방문한다.
        int index = 0;
        int min = int.MaxValue;
        for (int i = 1; i <= N; i++)
        {
        	// 방문하지 않은 정점 중
        	if (!visited[i])
            {
            	// 거리가 제일 짧은 정점
            	if (min > minDistance[i])
                {
                	min = minDistance[i];
                    index = i;
                }
            }
        }

		// min값이 초기화한 값(int.MaxValue)이라면 더이상 방문할 정점이 없다는 뜻.
        if (min == int.MaxValue)
        	break;

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

	// 도착 정점까지의 거리를 리턴한다.
    return minDistance[end];
}

 

지금까지는 다익스트라 알고리즘을 그대로 구현했을 뿐!

정말 중요한 것은 다음 단계이다.

 

이 문제는 어렵다기보다는 실수하기 쉬운 문제인데, 예외적인 상황이 많기 때문.

 

 (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 

 

v1는 v2가 될 수 없고, v1은 N이 될 수 없고, v2는 1이 될 수 없으나

v1 == 1, v2 == N은 가능하다는 소리다!

1 == N도 가능할 것으로 보이지만, 로직상 문제는 없어서 패스한다.

 

그리고 놓치기 쉬운 사실이 하나 더 있는데

경우의 수가 없을 경우 "-1"을 출력하는 것이다.

 

나는 하나하나 예외처리를 했는데, 코드를 살펴보도록 하자.

// 경우의 수를 생각하여 한 정점에서 다른 정점으로 가는 최솟값을 모두 구하였다.
// 변수 이름 그대로의 뜻.
int startToV1 = Dijkstra(1, v1);
int startToV2 = Dijkstra(1, v2);
int v1ToV2 = Dijkstra(v1, v2);
int v1ToEnd = Dijkstra(v1, N);
int v2ToEnd = Dijkstra(v2, N);
int startToEnd = Dijkstra(1, N);

// 1 -> N
if (1 == v1 && N == v2)
{
	if (startToEnd >= int.MaxValue)
		print.WriteLine(-1);
	else
		print.WriteLine(startToEnd);
	}
// 1 -> v2 -> N
else if (1 == v1)
{
	if (startToV2 >= int.MaxValue || v2ToEnd >= int.MaxValue)
		print.WriteLine(-1);
	else
		print.WriteLine(startToV2 + v2ToEnd);
}
// 1 -> v1 -> N
else if (N == v2)
{
	if (startToV1 >= int.MaxValue || v1ToEnd >= int.MaxValue)
		print.WriteLine(-1);
	else
		print.WriteLine(startToV1 + v1ToEnd);
}
// 나머지 경우는 모든 정점을 다 거치는 경우이다.
// 1 -> v1 -> v2 -> N or 1 -> v2 -> v1 -> N 
else
{
	if ((startToV1 >= int.MaxValue || v1ToV2 >= int.MaxValue || v2ToEnd >= int.MaxValue) 
    || (startToV2 >= int.MaxValue || v1ToV2 >= int.MaxValue || v1ToEnd >= int.MaxValue))
		print.WriteLine(-1);
	else
		print.WriteLine(Math.Min(startToV1 + v1ToV2 + v2ToEnd, startToV2 + v1ToV2 + v1ToEnd));
}

 

문제를 꼼꼼히 보자.

 

 

+ 다익스트라 문제에 대해 적응이 필요하다면 아래 문제를 추천한다.

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

1916번: 최소비용 구하기

 

 

전체 코드

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 N = int.Parse(inputs[0]);
            int E = int.Parse(inputs[1]);

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

            inputs = reader.ReadLine().Split();
            int v1 = int.Parse(inputs[0]);
            int v2 = int.Parse(inputs[1]);

            int startToV1 = Dijkstra(1, v1);
            int startToV2 = Dijkstra(1, v2);
            int v1ToV2 = Dijkstra(v1, v2);
            int v1ToEnd = Dijkstra(v1, N);
            int v2ToEnd = Dijkstra(v2, N);
            int startToEnd = Dijkstra(1, N);

            if (1 == v1 && N == v2)
            {
                if (startToEnd >= int.MaxValue)
                    print.WriteLine(-1);
                else
                    print.WriteLine(startToEnd);
            }   
            else if (1 == v1)
            {
                if (startToV2 >= int.MaxValue || v2ToEnd >= int.MaxValue)
                    print.WriteLine(-1);
                else
                    print.WriteLine(startToV2 + v2ToEnd);
            }
            else if (N == v2)
            {
                if (startToV1 >= int.MaxValue || v1ToEnd >= int.MaxValue)
                    print.WriteLine(-1);
                else
                    print.WriteLine(startToV1 + v1ToEnd);
            }
            else
            {
                if ((startToV1 >= int.MaxValue || v1ToV2 >= int.MaxValue || v2ToEnd >= int.MaxValue) || (startToV2 >= int.MaxValue || v1ToV2 >= int.MaxValue || v1ToEnd >= int.MaxValue))
                    print.WriteLine(-1);
                else
                    print.WriteLine(Math.Min(startToV1 + v1ToV2 + v2ToEnd, startToV2 + v1ToV2 + v1ToEnd));
            }

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

                int[] minDistance = new int[N + 1];
                for (int i = 1; i <= N; i++)
                {
                    minDistance[i] = int.MaxValue;
                }
                while (queue.Count > 0)
                {
                    (int v, int distance) = queue.Dequeue();

                    for (int i = 1; i <= N; i++)
                    {
                        if (distances[v, i] != 0)
                            minDistance[i] = Math.Min(distance + distances[v, i], minDistance[i]);
                    }

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

                    if (min == int.MaxValue)
                        break;

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

                return minDistance[end];
            }

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