노드간의 최단 거리를 구하는 알고리즘에는 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있다.

플로이드 워셜 알고리즘
모든 노드간의 최단 거리를 구하는 알고리즘
표(2차원 배열)를 만들어 중간 경유지에 따라 값을 계속 갱신시킨다.
(DP(동적 프로그래밍)에 base로 가지고있음.)

다익스트라 알고리즘
두 개의 노드 사이의 최단 거리를 구하는 알고리즘
새로운 노드를 방문할 때마다 최소 누적합을 저장한다.

폴로이드 워셜 알고리즘

폴로이드 워셜 알고리즘의 핵심은 start -> mid -> end 이다.

위의 그림에서 A->D로 바로 갈 수 있는 방법은 존재하지 않지만, mid를 B로 둔다면,
A->B->D로 가는 최단 경로가 생긴다.

이처럼 도중에 경유하는 mid 노드를 만들면
1. 바로 갈 수 없는 경로를 mid 노드 경유를 통해 갈 수 있게 해준다.
2. 최단 경로를 갱신할 수 있게 도와준다.

아래 그래프는 폴로이드 워셜 알고리즘에서 사용할 표이다.

base

표의 기본 베이스는 아래와 같다. A->A로는 갈 수 없으므로 x,y가 같은 경우 0을 넣어준다.
나머지를 INF로 해놓은 이유는 아직 어느 수가 들어갈지 모르기 때문이다.

	A	B	C	D	E
A	0	INF	INF	INF	INF
B	INF	0	INF	INF	INF
C	INF	INF	0	INF	INF
D	INF	INF	INF	0	INF
E	INF	INF	INF	INF	0

시작

A->B로 가는 최단거리는 3이다. 따라서 chart[A][B] 자리에 3을 넣어주어야 한다.
마찬가지로 D->B로 가는 최단거리는 1이기에 chart[D][B] 자리에 1을 넣어준다.
나머지는 이를 반복하면 된다.

	A	B	C	D	E
A	0	6	INF	INF	INF
B	2	0	4	5	INF
C	INF	INF	0	INF	5
D	2	1	INF	0	INF
E	INF	8	5	INF	0

A 경유

앞선 표에서 B->D로 가는 최단 경로는 5였다.

하지만 만약 B->A->D와 같이 도중에 A를 경유하게 된다면, 최단 경로는 2+2=>4가 된다.

	A	B	C	D	E
A	0	6	INF	INF	INF
B	2	0	4	5	INF
C	INF	INF	0	INF	5
D	2	1	INF	0	INF
E	INF	8	5	INF	0

나머지 B,C,D,E 경유 과정도 A와 비슷하게 진행하면 된다.

B 경유

	A	B	C	D	E
A	0	6	10	11	INF
B	2	0	4	5	INF
C	INF	INF	0	INF	5
D	2	1	5	0	INF
E	10	8	5	13	0

C 경유

	A	B	C	D	E
A	0	6	10	11	15
B	2	0	4	5	9
C	INF	INF	0	INF	5
D	2	1	5	0	10
E	10	8	5	13	0

D 경유

	A	B	C	D	E
A	0	6	10	11	15
B	2	0	4	5	9
C	INF	INF	0	INF	5
D	2	1	5	0	10
E	10	8	5	13	0

E 경유

	A	B	C	D	E
A	0	6	10	11	15
B	2	0	4	5	9
C	15	13	0	18	5
D	2	1	5	0	10
E	10	8	5	13	0

코드 설명

chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end])

start: A, mid: B, end: D 라고 할 때,
B를 경유하기 전까지, A->D는 Infinity였다.
B를 경유하면 A->B->D는 6+5=>11이다.

따라서 chart[A][D]는 Math.min(Infinity,11)의 결과인 11이 된다.

전체 코드

function floid(chart){
  for (let mid = 0; mid < chart.length; mid++) {
    for (let start = 0; start < chart.length; start++) {
      for (let end = 0; end < chart.length; end++) {
        chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end])
      }
    }
  }
  return chart;
}
const chart = [
  [0, 6, Infinity, Infinity, Infinity], 
  [2, 0, 4, 5, Infinity], 
  [Infinity, Infinity, 0, Infinity, 5], 
  [2, 1, Infinity, 0, Infinity], 
  [Infinity, 8, 5, Infinity, 0]
]
console.log(floid(chart));

프로그래머스 > 그래프 > 순위

function solution(n, results) {
  let answer = 0;
  // 선수 세팅
  const players = Array.from({length: n}, (v, i) => i+1);

  // 표 만들기
  const chart = Array.from({length: n+1}, () => Array(n+1).fill(false))
  results.map(result=>{
    const [win,lose] = result;
    chart[win][lose] = 1;
    chart[lose][win] = -1;
    chart[win][win] = 0;
    chart[lose][lose] = 0;
  })

  // floid-warshall 알고리즘 사용
  for(const mid of players){
    for(const start of players){
      for(const end of players){
        if(chart[start][mid]===1 && chart[mid][end]===1) chart[start][end] = 1;
        if(chart[start][mid]===-1 && chart[mid][end]===-1) chart[start][end] = -1;
      }
    }
  }

  // 1. 상단과 좌측의 false를 없앤다.
  // 2. false를 하나도 가지고 있지 않으면 answer++해줌
  chart.map(player=>{
    player.slice(1,player.length).every(p=>p!==false) && answer++;
  })  
  return answer;
}