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인 경우, $V_{i}$에서 $V_{j}$로의 비용은 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문: $V_{k}$를 거칠 경우에 대해..
- 2, 3번째 for문: 모든 경로에 대해서..
이전 단계에서 갱신된 비용(D[i][j])보다 $V_{k}$를 거쳐 가는 비용(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로 재설정 해주었다.

📌 참고하자

나의 코드(Github)