[알고리즘][BOJ]11404_플로이드

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⁰12345
1023110
202
38011
403
5740

12345
1023110
202
3810011
403
5741080

12345
1023110
202
3810011
403
5741060

12345
102314
202
3810011
403
5741060

D⁴12345
102314
2025
3810011
403
5741060

D⁵12345
102314
21201525
385011
41071303
5741060

💥 발전하자

  • 에러 및 해결
    처음에는 단일 비용의 최댓값이 100,000이기 때문에 INF를 999,999로 했었다. 하지만 갱신되는 과정에서 경로의 비용이 999,999를 넘을 수 있기 때문에(ex. ∞ -> 100,000,0) INF를 999,999,99로 재설정 해주었다.

📌 참고하자

나의 코드(Github)

좋은 웹페이지 즐겨찾기