스위프트 코딩테스트 강좌, 플로이드-워셜

코딩테스트에서 자주 등장하는 플로이드-워셜 알고리즘을 배우고 관련 알고리즘 문제를 해결해보겠습니다. 이 글에서는 플로이드-워셜 알고리즘의 개요, 동작 원리, 그리고 예제 문제 풀이 과정을 상세히 다룰 것입니다.

1. 플로이드-워셜 알고리즘 개요

플로이드-워셜 알고리즘은 그래프의 모든 정점 쌍 간의 최단 경로를 찾기 위한 알고리즘입니다. 이 알고리즘은 동적 프로그래밍을 기반으로 하며, 각 단계에서 정점 k를 거쳐가는 경로를 고려하여 최단 경로를 업데이트합니다. 플로이드-워셜 알고리즘의 시간 복잡도는 O(V³)입니다. 여기서 V는 정점의 수를 나타냅니다.

1.1. 알고리즘의 의의

플로이드-워셜 알고리즘은 단순히 단일 출발점과 최단 경로를 찾는 데 그치지 않고, 모든 정점 쌍 간의 최단 경로를 한 번의 과정을 통해 파악할 수 있다는 점에서 뛰어난 효율성을 보입니다.

1.2. 적용 사례

이 알고리즘은 네트워크의 모든 노드 간의 최단 경로 계산, 도로망 최적화, 게임에서의 이동 경로 계산 등 다양한 분야에 활용됩니다.

2. 알고리즘의 동작 원리

플로이드-워셜 알고리즘은 아래와 같은 방식으로 동작합니다.

그래프의 모든 간선에 대해 초기 최단 경로를 설정합니다. 직접 연결된 두 정점 간의 거리는 간선의 가중치로 설정하고, 나머지 쌍은 무한대로 설정합니다.
각 정점 k에 대해 모든 정점 i, j를 조합하여 다음과 같이 최단 경로를 업데이트합니다: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
이 과정을 모든 정점 쌍에 대해 반복합니다.

이 알고리즘은 정점 k를 거쳐가는 경로가 존재할 경우, 이를 통해 최단 경로를 찾을 수 있게 됩니다.

3. 예제 문제

문제 설명

다음은 플로이드-워셜 알고리즘을 이용하여 해결할 수 있는 문제입니다:

주어진 N개의 정점과 M개의 간선으로 구성된 방향 그래프가 있을 때, 각 정점 쌍 간의 최단 거리를 구하는 프로그램을 작성하시오. 간선의 가중치는 양의 정수로 주어지며, 두 정점 간의 간선이 없는 경우 무한대로 설정해야 한다.

문제 입력

첫 줄에 정점의 수 N(1 ≤ N ≤ 100)과 간선의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 각 간선의 시작 정점, 끝 정점, 가중치가 주어진다. 두 정점 간에 여러 개의 간선이 있을 경우 가중치가 가장 작은 간선만 고려한다.

문제 출력

각 정점 쌍 간의 최단 거리를 출력한다. 만약 최단 거리가 존재하지 않으면, INF를 출력해야 한다.

예제

입력:

출력:

        0 1 2 3
        INF 0 1 2
        INF INF 0 1
        2 1 2 0

4. 문제 풀이 과정

문제를 해결하기 위해 플로이드-워셜 알고리즘을 구현해보겠습니다. 다음은 문제 풀이의 단계별 과정입니다.

4.1. 초기 설정

먼저 N개의 정점과 M개의 간선을 사용하여 초기 거리 배열을 설정합니다. 직접 연결된 정점 간의 가중치는 주어진 값으로 설정하고, 연결이 없는 경우는 무한대로 설정합니다.

4.2. 거리 배열 초기화

        var N = 4
        var M = 7
        var dist = [[Int]](repeating: [Int](repeating: Int.max, count: N + 1), count: N + 1)
        
        for i in 1...N {
            dist[i][i] = 0
        }

이 코드에서는 거리 배열 dist를 무한대로 초기화하고, 자기 자신으로 가는 거리는 0으로 설정합니다.

4.3. 간선 정보 입력

        dist[1][2] = 1
        dist[1][3] = 3
        dist[2][3] = 1
        dist[2][4] = 2
        dist[3][4] = 1
        dist[4][1] = 2
        dist[4][2] = 3

이제 간선 정보를 사용하여 직접 연결된 정점 간의 가중치를 설정합니다. 여러 간선이 존재할 경우 최소 가중치로 업데이트합니다.

4.4. 플로이드-워셜 알고리즘 적용

        for k in 1...N {
            for i in 1...N {
                for j in 1...N {
                    if dist[i][j] > dist[i][k] + dist[k][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }

여기서 k는 중간 정점으로서, i에서 j로 가는 최단 경로를 업데이트합니다.

4.5. 결과 출력

        for i in 1...N {
            for j in 1...N {
                if dist[i][j] == Int.max {
                    print("INF", terminator: " ")
                } else {
                    print(dist[i][j], terminator: " ")
                }
            }
            print("")
        }

최종적으로 거리 배열을 출력하여 각 정점 간의 최단 거리를 확인합니다.

5. 결론

이번 강좌에서는 플로이드-워셜 알고리즘의 개념과 동작 원리를 배우고, 실제 문제를 해결하는 과정을 살펴보았습니다. 이 알고리즘은 모든 정점 쌍 간의 최단 경로를 효율적으로 찾을 수 있는 강력한 도구입니다. 알고리즘의 이해를 높이기 위해 다양한 예제를 풀어보는 것이 중요합니다. 여러분도 스위프트로 알고리즘 문제를 해결해보며 실력을 쌓아보세요!