다익스트라 알고리즘은 특정 s에서 e까지의 최단 거리를 구하는 데에 사용된다.
그렇다면 임의의 i에서 j까지의 최단거리를 구할 때에는?
그래프의 지점에 대해서 서로의 최단 거리를 구하면 된다.
참고 - 안경잡이 개발자
참고 - 이코테 강의(프리라이프님 정리)
다익스트라 알고리즘이(힙을 사용하지 않았을 때) O(n^2)의 시간복잡도를 가진다.
플로이드 워셜은 각 경로가 업데이트 될 때마다 모든 노드에 대해 한번 더 업데이트 하므로 O(v^3)의 시간 복잡도를 가진다.
플로이드 뭐셜 알고리즘의 핵심적인 부분은
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);이다.
이는 임의의 두 노드 i, j에 대해,
최단경로 테이블에 있는 i-j의 값과, i에서 임의의 노드 k를 거쳐 b로 가는 i-k + k-j의 값 중 더 작은 값으로 최단경로 테이블을 업데이트 하는 것이다.
따라서 k에 대한 반복문, i에 대한 반복문, j에 대한 반복문, 총 3개의 반복문이 필요하여 O(n^3)의 시간복잡도를 갖는 그리디 알고리즘의 일종이며, 탐색의 순서는 무관하다.
const inf = Number.MAX_SAFE_INTEGER; // 무한을 의미하는 값으로 2^53-1을 지정
// 노드의 개수 및 간선의 개수를 입력받기
const n = 4;
const m = 7;
// 간선 리스트와 가중치를 입력받기
const input = [
[1, 2, 4],
[1, 4, 6],
[2, 1, 3],
[2, 3, 7],
[3, 1, 5],
[3, 4, 4],
[4, 3, 2],
];
// 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
const graph = Array.from(Array(n + 1), () => Array(n + 1).fill(inf));
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
if (a === b) {
graph[a][b] = 0;
}
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (let index = 0; index < m; index++) {
// A에서 B로 가는 비용은 C라고 설정
const [a, b, c] = input[index];
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (let k = 1; k <= n; k++) {
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
// 도달할 수 없는 경우, 무한(inf)이라고 출력
if (graph[a][b] === inf) {
process.stdout.write("inf ");
}
// 도달할 수 있는 경우 거리를 출력
else {
process.stdout.write(`${graph[a][b]} `);
}
}
console.log();
}
[[inf,inf,inf,inf,inf],
[inf,0,4,8,6],
[inf,3,0,7,9],
[inf,5,9,0,4],
[inf,7,11,2,0]]
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0
위의 그래프는 아래와 같이 출력된다. (편의상 무한을 -로 정의)
[[-,-,-,-,-],
[-,0,-,-,-],
[-,-,0,-,-],
[-,-,-,0,-],
[-,-,-,-,0]]
k가 1일 때
[[-,-,-,-,-],
[-,0,4,-,6],
[-,3,0,7,-],
[-,5,-,0,4],
[-,-,-,2,0]]
k가 3일 때
[[-,-,-,-,-],
[-,0,4,-,6],
[-,3,0,7,-],
[-,5,-,0,4],
[-,7,-,2,0]]
k가 4일 때
[[-,-,-,-,-],
[-,0,4,8,6],
[-,3,0,7,-],
[-,5,-,0,4],
[-,7,-,2,0]]
프로그래머스 level 3 - 순위
프로그래머스 레벨 3 순위 문제
풀이 : [프로그래머스] 순위(Floyd-Warshall Algorithm) - 우석블로그 - 플로이드 워셜을 꼼꼼하게 잘 정리해주신 것 같다.
플로이드 워셜 알고리즘은
- 특정 노드의 상태가 업데이트 되었을 때
- 다른 모든 노드의 상태도 업데이트 되어야 한다.
그리고 O(n^3)이다.
그리디 알고리즘의 속성을 갖는 최단경로 알고리즘(다익스트라 알고리즘) + DP테이블이라는 특성으로 인해 플로이드 워셜을 몰라도 풀이할 수 있고, 그래서 완전탐색 알고리즘의 형태로 코딩테스트 문제로도 종종 나오는 것 같다. 실제로 '순위' 문제와 비슷한 형태의 문제를 코테에서 보았...(고 떨어졌음 ㅠ)
플로이드 워셜의 기본 템플릿은 아래와 같다.
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[i][j] > arr[i][k] + arr[k][j]) { // 원래 i->j 가 i->j->k 보다 길면
arr[i][j] = arr[i][k] + arr[k][j]; // 갱신
}
}
}
}
그리고 순위 문제는 앞에 온 노드가 이긴 경우의 그 다음 노드가 알아야 한다.
function solution(n, results) {
var answer = 0;
const distance = Array.from({length : n+1}, ()=> Array.from({length : n+1}, ()=>0))
results.forEach(( [winner, loser] ,index)=>{
distance[winner][loser] = 1 //winner가 loser를 이겼음을 표시
})
/*
해당 부분은 Floyd-Warshall 알고리즘을 구현한 부분입니다.
k는 경유지를 의미합니다. 즉, k를 경유해서 i에서 j로 갈 수 있는지 판별하는 것입니다. 이를 위해 3중 for문을 사용하여 i에서 j로 가는 경로를 탐색합니다. 이때, 만약 i가 j를 이긴 적이 없고 i가 k를 이겼고 k가 j를 이긴 적이 있다면, i는 j를 이길 수 있게 됩니다. 따라서 distance[i][j]를 1로 갱신합니다.
이 과정을 모든 k, i, j에 대해 반복하면서 distance 배열을 갱신하게 됩니다. 이를 통해 모든 선수들 간의 승패 여부를 판별할 수 있습니다.
*/
for (let k = 1; k < n+1; k++) { // path via k+1
for (let i = 1; i < n+1; i++) {
for (let j = 1; j < n+1; j++) {
// i+1 wins k+1 && k+1 wins j+1 -> i+1 wins j+1
if (distance[i][j] == 0 && distance[i][k] && distance[k][j]) {
distance[i][j] = 1;
}
}
}
}
/*
마지막으로, 각 선수들의 distance 배열에서 승패 여부를 추출하여 해당 선수가 순위를 매길 수 있는지 확인합니다. 이를 위해 각 행과 열의 승패 여부의 합을 계산합니다. 만약 각 행과 열의 승패 여부의 합이 n-1이면 해당 선수가 순위를 매길 수 있는 것으로 판별하여 answer 변수를 증가시킵니다.
*/
for(let i = 1; i < n + 1; i++) {
let rowSum = distance[i].reduce((a,b) => a+b)
let colSum = 0
for (let j = 1; j < n + 1; j++) {
colSum += distance[j][i]
}
if(rowSum + colSum === n - 1) {
answer += 1
}
}
return answer;
}