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

문제

https://programmers.co.kr/learn/courses/30/lessons/49191

해결

플로이드 와샬 알고리즘을 이용하여 각 노드의 인접한 노드의 개수와 n명이서 모두 경기를 치르는 경우(n-1)이 같다면 순위를 결정할 수 있습니다.

• 단방향으로 플로이드 와샬 알고리즘을 적용해 dist 배열 생성.
  1. 단방향으로 플로이드 와샬 알고리즘 적용.
  2. 대각선을 제외한 dist 배열의 값 0은 [from]->[to], 즉 [win]->[lose]의 관계를 나타냅니다.
  3. 인접한 노드의 개수를 새기 위해 정방향([win]->[lose])의 개수와 역방향([lose]->[win])의 개수를 셉니다.
  4. 자기 자신으로 중복으로 카운트된 2개를 뺀 갯수와 모두 경기를 치루는 경우 n-1이 같다면 순위를 결정할 수 있습니다.

const dist = [0,0,∞,∞,0]
	     [∞,0,∞,∞,0]
	     [∞,0,0,∞,0]	
	     [∞,0,0,0,0]
	     [∞,∞,∞,∞,0]

코드

function solution(n, results) {
  let answer = 0;
  let dist = Array.from(new Array(n), () => new Array(n).fill(9));

  // 대각선 설정
  for (let i = 0; i < n; i++) {
    dist[i][i] = 0;
  }

  results.forEach((result) => {
    const [from, to] = result;
    
    // 단방향 설정
    dist[from - 1][to - 1] = 0;
  });

  // 플로이드 와샬 알고리즘
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) continue;
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    let degree = 0;

    for (let j = 0; j < n; j++) {
      // 행 / 열 탐색
      if (dist[i][j] === 0) degree++;
      if (dist[j][i] === 0) degree++;
    }

    if (degree-2 === n - 1) answer++;
  }

  return answer;
}

피드백

순위를 결정하는 방법과 두 노드 간 최소 비용을 계산할 때만 사용해서 익숙해져서 그런지 플로이드 와샬 문제인 것을 깨닫지 못했습니다. 순서, 랭크와 같은 단방향 그래프에도 사용할 수 있다는 것을 알았습니다.