[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘이란? (feat.Swift)

 

안녕하세요 Foma🍍 입니다!

 

오늘은 그래프 문제에서 아주 빈번하게 사용되는 플로이드 와샬이라는 알고리즘에 대해서 알아보겠습니다.

 

바로 시작할게요!

---

플로이드 와샬이란? 🤔

 

위키 백과에는 다음과 같이 정의되어있습니다.

 

"플로이드 와샬 알고리즘은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다."

 

쉽게 말하면 모든 최단 경로를 찾는 알고리즘이에요.

---

그래프 설명

 

아래와 같은 그래프가 있다고 가정할게요.

 

(파란색 동그라미는 정점, 사이에 숫자는 거리입니다.)

만약 1번 정점에서 3번 정점으로 가려면 어떤 정점을 이용해야 가장 짧을까요?

 

정답을 알기 위해선 중간에 모든 정점을 거쳐서 간 다음 가장 짧은 거리를 구해야 할 것 입니다.

 

1번 -> 2번 -> 3번 32

 

1번 -> 5번 -> 3번 11

 

이므로 1번에서 5번을 거쳐 3번으로 가는 것이 가장 빠르겠죠?

 

또한 2번과 3번 같이 직접 연결되어 있다고 하더라도 2번에서 4번을 거쳐 3번으로 가는 경우가 훨씬 더 거리가 짧은 것을 알 수 있습니다.

 

(2번 -> 3번 20 2번 -> 4번 -> 3번 8)

 

이런 식으로 플로이드 와샬은 시작 : 1...n  중간: 1... n 도착: 1...n 까지 n의 3제곱으로 모든 경우의 수를 탐색합니다.

 

이렇게 모든 값을 찾아놓으면 어떤 정점이든 가장 짧은 거리를 알 수 있겠죠.

 

다음과 같이 6번처럼 절대로 가지 못하는 정점에 대한 것은 무한대로 값을 지정합니다.

 

---

코드 설명

 

몇개의 정점(n)이 있는지와 모든 정점의 연결에 대한 거리(allConnections)를 저장해둡니다.

let n = 6
let allConnections = [[1,2,12],[2,3,20],[3,4,5],[4,5,7],[1,5,10],[2,4,3]]

모든 거리를 저장할 Int.max로 이뤄져있는 이차원 배열을 n+1 제곱만큼 만들어줍니다.( 1번부터 시작하므로 0번째 인덱스를 무시하기 위해)

var allDistances = Array(repeating: Array(repeating: Int.max, count: n+1), count: n+1)

 

자기 자신의 거리는 0으로 세팅해줍니다.

for i in 1...n {
	allDistances[i][i] = 0
}

 

allConnections에 있는 모든 거리들을 allDistances에 담아줍니다.

func setConnection() {
    for connection in allConnections {
        allDistances[connection[0]][connection[1]] = connection[2]
        allDistances[connection[1]][connection[0]] = connection[2]
    }
}

플로이드 와샬 알고리즘을 통해 j가 직접 k로 가는 것과 i를 거쳐 k로 가는 것을 비교하여 더 작은 값으로 바꿔줍니다.

func floyd() {
    for i in 1...n {
        for j in 1...n {
            for k in 1...n {
                if allDistances[j][i] == Int.max || allDistances[i][k] == Int.max { continue }
                if allDistances[j][i] + allDistances[i][k] < allDistances[j][k] {
                    allDistances[j][k] = allDistances[j][i] + allDistances[i][k]
                }
            }
        }
    }
}

이렇게 하면 모든 정점에 대한 가장 빠른 거리를 구할 수 있습니다.

 

 

전체 소스 코드

 

let n = 6

let allConnections = [[1,2,12],[2,3,20],[3,4,5],[4,5,7],[1,5,10],[2,4,3]]

var allDistances = Array(repeating: Array(repeating: Int.max, count: n+1), count: n+1)

func setConnection() {
    for connection in allConnections {
        allDistances[connection[0]][connection[1]] = connection[2]
        allDistances[connection[1]][connection[0]] = connection[2]
    }
}

func floyd() {
    for i in 1...n {
        for j in 1...n {
            for k in 1...n {
                if allDistances[j][i] == Int.max || allDistances[i][k] == Int.max { continue }
                if allDistances[j][i] + allDistances[i][k] < allDistances[j][k] {
                    allDistances[j][k] = allDistances[j][i] + allDistances[i][k]
                }
            }
        }
    }
}

setConnection()
floyd()
print(allDistances)

---

관련 문제

 

2021 KAKAO BLIND RECRUITMENT 합승 택시 요금

 

[Swift] 2021 KAKO BLIND RECUITMENT 합승 택시 요금

 

 

프로그래머스 순위

 

[Swift] 프로그래머스 순위