1. 플로이드 와샬 알고리즘
- 그래프의 모든 노드에서 다른 모든 노드까지 최단거리를 구하는 알고리즘
- O(V^3)의 시간복잡도를 가졌다. 코드를 보면 알겠지만 3중 포문이 돌아간다.
- 매커니즘
- j노드에서 k노드를 바로 가는 것과 i를 거쳐서 가는 것 중 비교를 계속 진행한다.
2. 문제와 코드
- 프로그래머스 배달 문제 참고
class Solution{
public int solution(int N, int[][] road, int K) {
int answer = 0;
//거리 비용을 2차원 배열에 정리
int[][] costs = new int[N][N];
for (int i = 0; i < costs.length; i++) {
Arrays.fill(costs[i], 500001);
costs[i][i] = 0;
}
//노드 간 거리를 입력해준다.
for (int i = 0; i < road.length; i++) {
if (costs[road[i][0] - 1][road[i][1] - 1] > road[i][2]) {
costs[road[i][0] - 1][road[i][1] - 1] = road[i][2];
costs[road[i][1] - 1][road[i][0] - 1] = road[i][2];
}
}
//플로이드 와샬
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
// jk를 바로 가는 것과 i를 거쳐서 가는 것 중 비교한다.
costs[j][k] = Math.min(costs[j][k], costs[j][i] + costs[i][k]);
}
}
}
//기준 노드에서 다른 노드들까지 가는데 K 이하의 비용으로 가는 경우 계산
for (int i = 0; i < N; i++) {
if (costs[0][i] <= K) {
answer++;
}
}
return answer;
}
}
3. 참조
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr