[Algorithm] 순위

📋 문제

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

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

 

제한 사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

5

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

2

 

✏️ 풀이

정말 여러가지를 시도했던 문제였다. 첫 번째로 플로이드 와샬로 풀어보기도 했는데 테스트 케이스 몇개를 통과하지 못하는데 이유를 찾지 못해서 다른 방법으로 접근했다. 두 번째로는 DFS를 이용하는 방법이었는데 해결했다.

 

먼저 승패 결과를 graph에 저장했다. 승리했을 때, 패배했을 때로 두개의 graph를 따로 분리하고 key는 선수, value는 상대 선수를 배열로 관리했다. 그리고 선수를 하나하나 돌면서 DFS로 탐색했다.

 

처음에 생각을 잘못했던 점이 같은 선수를 중복으로 돌지 않기 위해 배열에 값을 저장하는 방법을 사용했는데 만약 2번 선수가 [5, 1] 총 2명의 선수에게 승리하여 배열에 저장해두고 4번 선수가 [1, 2] 선수에게 승리한 것을 계산할 때 2번 선수를 배열에 저장한 값을 가져오기 때문에 누가에게 승리했는지 알 수 없어 1번 선수가 중복되는 것을 계산하는 것이 불가능했다.

 

그래서 고민을 해보니 선수는 100명이 최대이기 때문에 dfs의 깊이는 최대 100이므로 최악의 경우에도 10000의 경우밖에 없다는 것을 알았다. 그래서 모든 선수를 순회하면서 승리, 패배한 선수를 체크하는 체크 배열(checkWin, checkLose)을 2개 만들어 DFS에 넘겨주고 DFS를 돌면서 승패 여부를 체크하고 DFS가 종료되면 이 체크배열을 reduce를 사용해 합을 구해 더해서 승패를 알고 있는 선수가 n - 1(모든 선수 - 자기 자신)과 같다면 자신이 몇 순위인지 정확하게 알 수 있다는 의미이므로 answer에 1을 더해줌으로서 해결했다.

 

⌨️ 코드

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

  const graphWinner = {};
  const graphLoser = {};

  for (const result of results) {
    const [winner, loser] = result;
    if (!graphLoser[winner]) graphLoser[winner] = [];
    graphLoser[winner].push(loser);

    if (!graphWinner[loser]) graphWinner[loser] = [];
    graphWinner[loser].push(winner);
  }

  const dfs = (player, type, check) => {
    const opponents = type === 'win' ? graphWinner[player] : graphLoser[player];
    if (!opponents) return;

    for (const opponent of opponents) {
      if (check[opponent]) continue;
      dfs(opponent, type, check);
      check[opponent] = 1;
    }

    return;
  };

  for (let player = 1; player < n + 1; player++) {
    const checkWin = new Array(n + 1).fill(0);
    const checkLose = new Array(n + 1).fill(0);

    dfs(player, 'win', checkWin);
    dfs(player, 'lose', checkLose);

    const cntWin = checkWin.reduce((a, b) => a + b, 0);
    const cntLose = checkLose.reduce((a, b) => a + b, 0);

    if (cntWin + cntLose === n - 1) answer += 1;
  }

  return answer;
}