[알고리즘][BOJ]11404_플로이드
💡 생각하자
[Dynamic Programming(동적 계획법)의 개발절차]
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기
재귀 관계식
D(k)[i][j] = minimun(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
💻 구현하자
- D 배열을 초기화 하는 함수
#define INF 99999999
// init
for (int i = 1;i < n + 1;i++) {
for (int j = 1;j < n + 1;j++) {
if (i == j)
D[i][j] = 0;
else
D[i][j] = INF;
}
}
i = j인 경우, Vi에서 Vj로의 비용은 0이다.
나머지는 임의의 큰 값(INF)로 초기화 해준다.
- 플로이드-와샬 알고리즘
void floyd(int n) {
for (int k = 1;k <= n;k++) {
for (int i = 1;i < n + 1;i++) {
for (int j = 1;j < n + 1;j++) {
if (D[i][j] > D[i][k] + D[k][j])
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
- 1번째 for문: Vk를 거칠 경우에 대해..
- 2, 3번째 for문: 모든 경로에 대해서..
이전 단계에서 갱신된 비용(D[i][j])보다 Vk를 거쳐 가는 비용(D[i][k] + D[k][j])이 더 작을 경우, 새로 갱신해준다.
- 초기 호출문
floyd(n);
실제 갱신 과정
D⁰ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 10 |
2 | ∞ | 0 | ∞ | 2 | ∞ |
3 | 8 | ∞ | 0 | 1 | 1 |
4 | ∞ | ∞ | ∞ | 0 | 3 |
5 | 7 | 4 | ∞ | ∞ | 0 |
D¹ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 10 |
2 | ∞ | 0 | ∞ | 2 | ∞ |
3 | 8 | 10 | 0 | 1 | 1 |
4 | ∞ | ∞ | ∞ | 0 | 3 |
5 | 7 | 4 | 10 | 8 | 0 |
D² | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 10 |
2 | ∞ | 0 | ∞ | 2 | ∞ |
3 | 8 | 10 | 0 | 1 | 1 |
4 | ∞ | ∞ | ∞ | 0 | 3 |
5 | 7 | 4 | 10 | 6 | 0 |
D³ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 4 |
2 | ∞ | 0 | ∞ | 2 | ∞ |
3 | 8 | 10 | 0 | 1 | 1 |
4 | ∞ | ∞ | ∞ | 0 | 3 |
5 | 7 | 4 | 10 | 6 | 0 |
D⁴ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 4 |
2 | ∞ | 0 | ∞ | 2 | 5 |
3 | 8 | 10 | 0 | 1 | 1 |
4 | ∞ | ∞ | ∞ | 0 | 3 |
5 | 7 | 4 | 10 | 6 | 0 |
D⁵ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 2 | 3 | 1 | 4 |
2 | 12 | 0 | 15 | 2 | 5 |
3 | 8 | 5 | 0 | 1 | 1 |
4 | 10 | 7 | 13 | 0 | 3 |
5 | 7 | 4 | 10 | 6 | 0 |
💥 발전하자
- 에러 및 해결
처음에는 단일 비용의 최댓값이 100,000이기 때문에 INF를 999,999로 했었다. 하지만 갱신되는 과정에서 경로의 비용이 999,999를 넘을 수 있기 때문에(ex. ∞ -> 100,000,0) INF를 999,999,99로 재설정 해주었다.
📌 참고하자
Author And Source
이 문제에 관하여([알고리즘][BOJ]11404_플로이드), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyhking/알고리즘BOJ11404플로이드저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)