99클럽 코테 스터디 2일차 TIL + Floyd-Warshall
오늘의 문제
https://www.acmicpc.net/problem/12956
Floyd-Warshall 알고리즘
문제의 힌트가 Floyd-Warshall 알고리즘이라 해당 알고리즘에 대해 짧게 공부해봤다.
최단 경로를 구할 때 사용하는 알고리즘이다.
다익스트라 알고리즘과 함께 공부하고 비교되는 알고리즘이다.
모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘이다.
2차원 배열에 최단 거리 정보를 저장해야 한다.
노드 N개에 대해서 N번만큼 단계를 반복하며 아래 코드를 적용해 2차원 배열을 갱신해야 한다.
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
알고리즘의 대략적인 흐름은 아래와 같다.
- step 1 : 모든 노드에 대해 A 노드에서 B 노드까지 직접 연결된 간선으로 최단 거리 저장하는 2차원 배열 갱신
- step 2 : 0번 노드 거쳐가는 경우를 체크하며 최단 거리 저장하는 2차원 배열 갱신 (graph[i][j], graph[i][0]+graph[0][j])
- step 3 : 1번 노드 거쳐가는 경우를 체크하며 최단 거리 저장하는 2차원 배열 갱신 (graph[i][j], graph[i][1]+graph[1][j])
- step 4 : ....
- step 5 : N번 노드 거쳐가는 경우를 체크하며 최단 거리 저장하는 2차원 배열 갱신 (graph[i][j], graph[i][N]+graph[N][j])
알고리즘 구현 순서는 아래와 같다.
- 2차원 배열 구현 후 모든 칸을 무한대로 초기화 (무한대 = 매우 큰 값)
- 자기 자신으로 가는 비용은 0으로 초기화 (graph[i][i] = 0)
- 주어진 간선 정보에 따라 위의 step 1을 진행
- step 2~5 진행
step 2~5가 중요한데 이때 3중 for문을 아래와 같이 사용한다.
for(int k=0; k<node; k++){ // -> k = 거쳐갈 노드
for(int i=0; i<node; i++){ // -> i = 출발 노드 (행)
for(int j=0; j<node; j++){ // -> j = 도착 노드 (열)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j];
}
}
}
이렇게 3중 for문을 사용하기 때문에 Floyd-Warshall 알고리즘의 시간 복잡도는 O(n^3)이다.
n은 node의 개수이다.
회고
Floyd-Warshall 알고리즘을 알고 나니 어떻게 풀지가 보였다.
Floyd-Warshall 알고리즘을 적용해 각 노드까지의 최단 거리를 구해 놓는다.
그리고 각 간선을 하나씩 뺀채로 Floyd-Warshall 알고리즘을 돌려 간선이 없을 때의 각 노드까지의 최단 거리를 구한다.
그리고 원래의 최단 거리와 비교하면 된다고 생각하였다.
또 그렇게 코드를 작성하고 다른 사람들이 공유한 코드와 비교해도 문제가 없는 것 같았다.
그런데 계속 1%에서 실패했다.
질문 게시판에 다른 사람들이 질문한 것도 없어서 왜 틀린지를 알 수가 없다.
디스코드의 질문 게시판에 올려두었는데 이유를 알고 통과하게 된다면 추가로 작성해보겠다.
틀린 이유 후기
위의 설명에서 3중 for문 사용할 때 잘 k, i, j 순으로 해 놓고서는 실제 문제 풀 때는 나도 모르게 습관적으로 i, j, k로 써서 계속 틀렸던 것이였다.....
문제를 잘 만든게 i, j, k로 하면 예제들은 다 통과한다 ㅋㅋㅋㅋ;;
질문 게시판에 질문도 없어서 밤에는 계속 안보이고 헤맸다....
아침에 다시 한번 개운하게 일어나서 보니 이제야 보였다...
역시 알고리즘 문제는 안 풀리면 자고 일어나서 해야 하는 것 같다.