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

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.

• 경기 결과는 1개 이상 4,500개 이하입니다.

• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.

• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

 

 

나의 풀이

 쉽게 봤다가 큰 코 다친 문제... 아이고난! 플로이드 와샬 알고리즘을 이용해서 풀었다. 물론 자체적으로 풀진 않고 다른 분의 코드를 참고했다. 풀이는 다음과 같다.

 

 

1. 플로이드 와샬 알고리즘을 이용해서 단 방향 그래프의 이동 경로 유무를 설정해 준다. 예를 들어 위 그림을 보면, 1번은 2번을 거쳐 5번까지 갈 수 있다. 단 방향 그래프가 가리키는 방향은 자신이 가리키는 상대를 시합에서 이겼을 경우다. 이를 해석하면, 1번은 2번을 이겼고, 2번은 5번을 이겼다. 따라서 1번은 5번을 항상 이길 수 있다는 것이다.

 

 

2. 각 정점마다 인접한 정점의 개수를 샌다. Infinity와 자기 자신은 제외

 

 

3. 다른 정점에 자신이 연결되어있는지 유무를 검사하여, 연결되어 있다면 이전에 정점의 개수의 값이 1을 더한다. 이 과정을 거치는 이유는 현재 선수가 몇 번의 시합을 치뤘는지 검사하기 위해서다.

 

 

4. 정점의 개수(시합을 치른 횟수) 값이 n과 같다면 순위를 매길 수 있는 선수가 있다는 것을 알 수 있다.

 

const solution = (n, results) => {
  const graph = Array.from({length:n}, () => new Array(n).fill(Infinity));
  let answer = 0;
  
  for(let i=0; i<graph.length; i++)
    graph[i][i] = 0;

  for(let i=0; i<results.length; i++){
      const [win, lose] = results[i];
      graph[win-1][lose-1] = 0;
  }

  for(let k=0; k<graph.length; k++){
    for(let i=0; i<graph.length; i++){
      if(graph[i][k] === Infinity) continue;
      for(let j=0; j<graph.length; j++){
        if(i === k || j === k || graph[k][j] === Infinity) continue;
        graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
      }
    }
  }

  graph.map((row, idx) => {
    let degree = 0;
    row.map(v => v===0 ? degree++ : null);

    for(let i=0; i<n; i++){
      if(i===idx) continue;
      graph[i][idx] === 0 ? degree++ : null;
    }

    if(degree === n)  answer++;
  })

  return answer;
}