C# 코딩테스트 강좌, 플로이드-워셜

날짜: 2023년 10월 1일

서론

알고리즘 문제는 코딩테스트에서 중요한 요소 중 하나로, 특히 그래프 알고리즘은 많은 상황에서 유용하게 활용됩니다.
이 글에서는 플로이드-워셜 알고리즘을 활용한 문제를 풀이해보겠습니다.
플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾기 위한 알고리즘으로, 주로 동적 프로그래밍 기법을 사용합니다.

문제 설명

문제: 최단 경로 찾기

자신이 다니는 대학교의 모든 캠퍼스는 정점으로 표현되고, 캠퍼스를 연결하는 도로는 간선으로 표현됩니다.
캠퍼스 A에서 캠퍼스 B까지 가는 최단 경로의 거리를 구해보세요. 아래의 입력 형식을 따릅니다.

            입력:
            - 첫 번째 줄: 총 캠퍼스의 개수 N (1 ≤ N ≤ 100)
            - 두 번째 줄: 도로의 개수 M (1 ≤ M ≤ 10000)
            - 다음 M 줄: 각 도로의 정보 (A, B, C) 형식으로 주어지며, A에서 B로 가는 도로의 길이가 C임을 의미합니다.
            
            출력:
            - 캠퍼스들 간의 최단 경로의 거리 행렬을 출력하시오.

알고리즘 개요

플로이드-워셜 알고리즘은 다음과 같은 기본 원리에 기반합니다.
모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 k를 경유할 경우의 거리와 직접 경로의 거리를 비교하여 최단 경로를 갱신하는 방식입니다.

            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

이 알고리즘은 O(N^3)의 시간 복잡도를 가지며, 모든 정점 쌍 간의 최단 경로를 효율적으로 구할 수 있습니다.

문제 풀이 과정

1단계: 입력 처리

입력을 처리하기 위해, 배열을 초기화하고 도로 정보를 입력받습니다.
거리를 무한대로 초기화한 후, 직접 연결된 캠퍼스 간의 거리를 입력받아 설정합니다.
이를 통해 초기 거리 행렬 D를 만듭니다.

2단계: 플로이드-워셜 알고리즘 구현

세 개의 중첩 루프를 통해 각 캠퍼스 쌍 간의 최소 거리를 갱신합니다.
각 반복에서 k를 경유할 경우 더 짧은 경로가 있는지를 체크하고, 그 경우 거리 행렬을 업데이트 합니다.

3단계: 결과 출력

업데이트된 거리 행렬을 출력합니다. 무한대로 남아있는 경우는 도달할 수 없는 캠퍼스를 의미합니다.

C# 코드 구현

            
            using System;
            using System.Linq;

            class Program
            {
                const int INF = 987654321; // 무한대 값 정의

                static void Main(string[] args)
                {
                    // 입력 처리
                    int N = int.Parse(Console.ReadLine());
                    int M = int.Parse(Console.ReadLine());

                    int[,] D = new int[N + 1, N + 1];

                    // 거리 배열 초기화
                    for (int i = 1; i <= N; i++)
                    {
                        for (int j = 1; j <= N; j++)
                        {
                            if (i == j) D[i, j] = 0;
                            else D[i, j] = INF; // 무한대로 초기화
                        }
                    }

                    // 도로 정보를 거리 배열에 입력
                    for (int i = 0; i < M; i++)
                    {
                        var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                        int A = input[0], B = input[1], C = input[2];
                        D[A, B] = Math.Min(D[A, B], C); // 여러 개의 도로가 있을 수 있으니 최소값으로 설정
                    }

                    // 플로이드-워셜 알고리즘
                    for (int k = 1; k <= N; k++)
                    {
                        for (int i = 1; i <= N; i++)
                        {
                            for (int j = 1; j <= N; j++)
                            {
                                D[i, j] = Math.Min(D[i, j], D[i, k] + D[k, j]);
                            }
                        }
                    }

                    // 결과 출력
                    for (int i = 1; i <= N; i++)
                    {
                        for (int j = 1; j <= N; j++)
                        {
                            if (D[i, j] == INF) Console.Write("INF ");
                            else Console.Write(D[i, j] + " ");
                        }
                        Console.WriteLine();
                    }
                }
            }

결론

이번 글에서는 플로이드-워셜 알고리즘을 이용한 최단 경로 찾기 문제를 다루었습니다.
이 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 데 효과적이며, 실제 상황에서도 널리 사용됩니다.
다양한 그래프 문제를 풀기 위해 플로이드-워셜 알고리즘을 잘 이해하고 활용하시길 바랍니다.

서론