서문

요즘 Jest와 다른 공부들을 하다보니까 시간이 모자라 하루에 한 문제씩 풀지 못하고 놓치는 경우가 생기고 있다... ㅠ ㅠ
시간관리를 잘 하지 못한 내 핑계지만 놓친만큼 주말에 최대한 맞춰야겠다.

이번 문제는 처음에는 어떻게 이거를 그래프로 풀지 싶었는데 고민하다보니까 접근법이 생각나서 이를 토대로 구현해보았다. 그러다가 은근 시간이 걸렸고 그러다보니 다른 사람들은 이 문제를 어떻게 접근했을지 너무 궁금한 문제였다.

소스 코드

/*
  제한 사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
*/
function solution(n, results) {
  let answer = 0;
  const adjArray = new Array(n + 1);
  for (let i = 1; i <= n; i++) {
    adjArray[i] = new Array(n + 1).fill('');
  }

  results.forEach(result => {
    adjArray[result[0]][result[1]] = 'W';
    adjArray[result[1]][result[0]] = 'L';
  });

  Loop: for (let i = 1; i <= n; i++) {
    const winQ = [i];
    const loseQ = [i];
    const winV = [];
    const loseV = [];
    let winCnt = 0;
    let loseCnt = 0;

    while (winQ.length !== 0) {
      if (winCnt + loseCnt === n - 1) {
        answer++;
        continue Loop;
      }

      const current = winQ.shift();

      for (let j = 1; j <= n; j++) {
        if (adjArray[current][j] === 'W' && !winV.includes(j)) {
          winCnt++;
          winQ.push(j);
          winV.push(j);
        }
      }
    }

    while (loseQ.length !== 0) {
      if (winCnt + loseCnt === n - 1) {
        answer++;
        continue Loop;
      }

      const current = loseQ.shift();

      for (let j = 1; j <= n; j++) {
        if (adjArray[current][j] === 'L' && !loseV.includes(j)) {
          loseCnt++;
          loseQ.push(j);
          loseV.push(j);
        }
      }
    }
  }

  return answer;
}

문제 풀이

인접 행렬을 구성하여 해결했다. 먼저 인접행렬을 만들어주고, 그 후 각 요소에 이겼으면 'W', 졌으면 'L'을 대입해줬다.

그 다음 인접행렬을 바탕으로 그래프를 BFS로 탐색하기로 했다. 근데 이긴 것만 확인하는 탐색과 진 것만 확인하는 탐색 두 단계로 나눠서 진행해서 아래와 같이 변수들을 선언해줬다.

    const winQ = [i];
    const loseQ = [i];
    const winV = [];
    const loseV = [];
    let winCnt = 0;
    let loseCnt = 0;

winQ와 loseQ는 각각 BFS를 돌면서 사용하기 위한 큐다. 그리고 winV와 loseV는 각 큐의 방문노드 확인을 위한 배열이고, winCnt와 loseCnt는 각각 이긴 노드 수와 진 노드 수를 세어주기 위한 변수다.

각 노드마다 인접 행렬을 바탕으로 이긴 노드가 몇 개인지, 진 노드가 몇 개인지 BFS로 탐색하면서 세어준다. 이겼으면 winCnt를 1 증가시켜주고 졌으면 loseCnt를 1 증가시켜줬다.

그러다가

if (winCnt + loseCnt === n - 1) {
    answer++;
    continue Loop;
}

위와 같이 이긴 수와 진 수가 n-1과 같아지면 더 이상 확인할 필요가 없으므로 정답을 하나 증가시켜주고 다음 노드를 탐색하게끔 해줬다.

winCnt + loseCnt 의 합이 n-1과 같다는 의미는 자신을 제외한 모든 노드와 비교가 되었다는 뜻이므로 자신의 정확한 순위를 안다는 의미이다. 그래서 정답인 answer를 1증가시켜 준 것이다.

이렇게 모든 노드를 탐색하면 최종 답이 answer에 담겨있을 것이고 이를 반환하면 정답이다.

후기

다른 사람의 풀이를 보지 않고 내 생각대로만 풀다보니까 생각보다 시간이 좀 걸렸다. 하지만 그만큼 뿌듯했고, 이제 어느정도 BFS가 익숙해져서 자신감도 생겼다.

이제 다른 사람들은 어떻게 이 문제를 접근했는지, 다른 알고리즘으로도 풀 수 있는지 확인해봐야겠다. 다른 사람의 코드를 보는 것도 큰 공부가 되기때문이다.