[SW 정글 24일차] 플로이드 와샬 알고리즘이 궁금하다

오늘은 DFS, BFS, 위상정렬을 공부하는 마지막 날로 복습을 하고 다른 동료들의 블로그를 보며 어떻게 문제에 접근했는지 살펴보았다.

그 중에서 알고리즘 공부를 꽤 하고 왔던 동료의 블로그를 보게 되었고 새롭고 신기한 알고리즘을 알게 되었다.

https://kspsd.tistory.com/15

백준 2617 구슬 찾기(python)

문제를 보고 플로이드 와샬 알고리즘이 떠올라서 적용을 한 것이다.

개인적인 시간이 부족했다면 플로이드 와샬 알고리즘을 알아보는 것을 나중의 계획으로 잡았겠지만 오늘 알아볼 시간이 있어 궁금증을 해소해보려고 한다.

 

 

 

1. 플로이드 와샬 알고리즘이란?

플로이드 와샬 알고리즘은 그래프를 탐색하고자 할 때 사용할 수 있는 알고리즘으로 그래프 내의 모든 정점에서 모든 정점으로의 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다.

플로이드 와샬 알고리즘의 핵심은 '거쳐가는 정점'을 기준으로 최단 경로를 구하는 것이다.

그리고 플로이드 와샬 알고리즘의 특징 중 하나는 음의 간선, 가중치가 음수인 경우에도 사용할 수 있다는 것이다.

크게 보면 플로이드 와샬 알고리즘과 같은 범주에 있는 다익스트라 알고리즘 같은 경우에는 음의 간선이 있으면 사용할 수 없다.

오늘의 주제는 플로이드 와샬 알고리즘이므로 다익스트라에 대한 설명은 따로 하지 않으려고 한다.

 

플로이드 와샬 알고리즘의 시간복잡도는 O(n^3)으로 시간복잡도만 봤을 때는 그리 효율적이지 않아보이지만 n이 어느정도 작고 모든 정점에서 모든 정점까지의 최단 거리를 구해야한다면 다른 그래프 탐색 알고리즘보다 효율적이고 이용할만한 알고리즘이라고 생각한다.

 

 

 

 

2. 플로이드 와샬 과정 보기

플로이드 와샬 알고리즘이 어떠할 때 쓸 수 있는지 알아봤으니 플로이드 와샬 알고리즘을 사용할 때 어떠한 과정으로 이루어지는지 알아보자.

먼저, 플로이드 와샬 알고리즘을 사용하기 위한 그래프는 아래와 같다.

플로이드 와샬 알고리즘을 적용하기 위해 해당 그래프의 정보를 인접행렬(matrix)로 만들어 준다.

matrix[i][j]의 원소는 i번째 노드부터 j 번째 노드까지의 가중치를 의미하게 된다.

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	8	INF	-4
2	0	INF	0	INF	1	7
3	0	INF	4	0	INF	INF
4	0	2	INF	-5	0	INF
5	0	INF	INF	6	0	0

인덱스번호를 맞추기 위해 0번 인덱스 행과 열은 0으로 채우고 노드끼리 연결되어 있지 않다면 INF(무한값)으로 초기값을 주었다.

이제 이 초기행렬을 시작으로 해서 모든 정점으로부터 모든 정점까지의 최단 거리를 구해야한다.

최단 거리를 구하기 위해 사용되는 수식은 아래와 같다.

d_ij라는 것의 의미는 i정점에서부터 j정점까지의 거리를 의미한다.

여기서 (k)라는 지수가 붙었는데 그 의미는 i정점에서 j정점까지의 사이에 k정점이 추가되었을 때 거리를 의미한다.

즉, i에서부터 j까지 쭉 가는 길이 최단 거리일 수도 있고 i에서 k까지 가고 다시 k에서 j까지 가는 거리가 더 짧은 거리가 될 수도 있다는 것이다.

그 수식을 표현한 것이 k >=1일 경우의 수식이다.

k=0일 때는 당연히 중간에 정점이 없으므로 초기행렬의 matrix[i][j]값이 되는 것이다.

 

그러면 어떠한 반복적인 작업을 통해서 i와 j사이에 존재하는 정점들을 찾으면서 정점이 있다면 수식을 적용하여 최단 거리를 찾으면 되겠구나라는 생각이 든다.

코드로 구현한다고 하면 아래와 같이 3중 for문을 쓰면 된다.

#n: 정점의 개수
#k: 경유지
for k in range(1, n + 1):
    #i: 출발지
    for i in range(1, n + 1):
        #j: 목적지
        for j in range(1, n + 1):
            matrix[i][j] = min(matrix[i][j], matrix[i][j] + matrix[k][j])

 

 

플로이드 와샬 알고리즘을 공부하면서 느낀 것은 BFS, DFS보다 생각할 요소는 적다는 느낌이다.

그래프를 인접행렬로 나타내고 3중 for문을 돌면서 최단거리를 찾아주면 된다.

하지만, 어떠한 문제를 봤을 때 '아! 그냥 BFS, DFS 쓰는 것보다는 플로이드 와샬 알고리즘 쓰면 되겠네'라는 생각을 가지는게 굉장히 어려운 것같다.

반드시 플로이드 와샬 알고리즘을 사용해야하는 문제를 만났을 때 떠올려서 사용할 수 있기를...

 

 

---

 

[오늘의 나는 어땠을까?]

오늘은 주어진 문제들을 복습하고 새로운 문제를 풀어보았다.

역시나 DFS, BFS를 이해해도 문제에 적용하는 것은 항상 새롭고 어렵다.

하지만, 5개월 동안 반복적인 학습을 한다면 수료 후에는 어느정도 실력이 갖춰질 수 있다고 생각하며 노력을 하고 있다.

 

내일도 지난 번과 마찬가지로 모의고사가 진행되는데 목표는 언제나 3개를 푸는 것이다.

조금 이상적인 목표라고 생각하고 현실적인 문제는 2문제 정도는 접근해서 풀고 동료들 앞에서 내 풀이를 발표하는 기회를 가지는 것이다.

목표를 이루기 위한 준비는 완벽하다고는 자신할 수 없지만 충분히 노력했다고 생각한다.

그리고 목표를 이룸에 있어 객관화된 지표로 나의 성장을 느낄 수 있기때문에 목표를 이룰 것이고 목표를 못이루더라도 자책보다는 피드백을 하는 태도를 가질 것이다.

 

 

---

<참고 자료>

https://seoyoung2.github.io/algorithm/2020/07/22/Floyd-Warshall.html

https://ssungkang.tistory.com/entry/Algorithm-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://chanhuiseok.github.io/posts/algo-50/

https://blog.naver.com/ndb796/221234427842