[프로그래머스 / JS ] 순위

Problem | 순위

🕊 난이도

level 3

📣 풀이 방법

✔️ 플로이드-와샬 방법을 사용한다.

1. 2차원 배열을 만든다.
   - 기본은 Infinity 값으로 채워준다.

   • [win][lose] 즉, a가 b를 이기면 true 로 채워준다.
   • [lose][win] b가 a에게 지면 false로 채워준다.
     
     

2. 플로이드 와샬을 이용하여 그래프를 순회한다.

   • i가 k를 이기고, k가 j를 이기면 [i][j]는 true 다.
   • i가 k에게 지고, k가 j에게 진다면 [i][j]는 false다.

3. 만약 본인을 제외하고 Infinity 값이 남아있다면 순위를 알 수 없는 경우다.

📄 전체 풀이

function solution(n, results) {
  var answer = 0;

  const graph = Array.from(Array(n + 1), () => Array(n + 1).fill(Infinity));

  for (let [win, lose] of results) {
    graph[win][lose] = true;
    graph[lose][win] = false;
  }

  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        if (graph[i][j] === Infinity) {
          if (graph[i][k] === true && graph[k][j] === true) graph[i][j] = true;
          if (graph[i][k] === false && graph[k][j] === false)
            graph[i][j] = false;
        }
      }
    }
  }

  for (let i = 1; i <= n; i++) {
    let cnt = 0;
    for (let j = 1; j <= n; j++) {
      if (i === j) continue;
      if (graph[i][j] !== Infinity) cnt++;
    }
    if (cnt === n - 1) answer++;
  }

  return answer;
}