폴로이드 워셜 알고리즘 with JS

자몽·2022년 3월 21일
1

알고리즘

목록 보기
27/31

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

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

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

폴로이드 워셜 알고리즘

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

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

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

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

base

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

ABCDE
A0INFINFINFINF
BINF0INFINFINF
CINFINF0INFINF
DINFINFINF0INF
EINFINFINFINF0

시작

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

ABCDE
A06INFINFINF
B2045INF
CINFINF0INF5
D21INF0INF
EINF85INF0

A 경유

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

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

ABCDE
A06INFINFINF
B2045INF
CINFINF0INF5
D21INF0INF
EINF85INF0

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

B 경유

ABCDE
A061011INF
B2045INF
CINFINF0INF5
D2150INF
E1085130

C 경유

ABCDE
A06101115
B20459
CINFINF0INF5
D215010
E1085130

D 경유

ABCDE
A06101115
B20459
CINFINF0INF5
D215010
E1085130

E 경유

ABCDE
A06101115
B20459
C15130185
D215010
E1085130

코드 설명

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;
}
profile
꾸준하게 공부하기

0개의 댓글