64.md

순위

플로이드 와샬 알고리즘?? 그거 알아야만함??

이 문제의 첫인상은 문제가 짧아서 좋았다 이다. 그런데 문제를 이해하고 나서 음 순위를 어떻게 나열할 수 있지?

내 생각의 흐름을 한번 정리해보자.

INPUT

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

위의 이미지처럼 생각하다보니 각각의 노드를 저런 식으로 표현해야만 랭킹을 알 수 있는 것아닐까, 라는 생각을 하게 되었고, 내가 알고 있는 지식으로는 저걸 표현할 수 없겠다 라는 생각이 들어서 이것 저것 참고를 하기 시작했다. 결론적으로 플로이드 와샬 알고리즘을 활용해서 푸는 것으로 설명이 되어 있다. 하지만 나는 해당 알고리즘을 공부하지 않고, 문제 자체만으로 접근해보기로 했다.

글 다 쓰고 회고하자면,,,

내가 알고 있는 지식으로는 저걸 표현할 수 없겠다 라는 생각 : 결론적으로 뭐든지 배열을 통해서 나열해보도록 하자!(특히나 비정형이라면 `2차배열``)

한 사람의 등수를 알기 위해선, 그 사람과 연결된 모든 사람과의 경기 결과를 알아야만 한다. → n명의 선수가 있을 때, 각 선수는 n-1번의 승패를 알 수 있어야 순위를 확정 지을 수 있다. (...라고 어떤 블로그에서 말했다.)

위 의미를 이해하고 다시 이미지를 살펴보자. 2번 기준으로 보면, INPUT에서는 [4,2] [3,2] [1,2] [2,5] 총 4명과의 승패를 알 수 있다.

(승 > 패)
4 > 2
3 > 2
1 > 2
2 > 5

총 5명 중에서 4명과의 경기 결과를 알기 때문에 2번은 4등이라는 등수를 매길 수 있다.

그렇다면 5번은 어떻게 등수를 매길수 있을까? INPUT에서 5번과의 경기 결과는 [2, 5] 한가지 밖에 없다.

(승 > 패)
2 > 5

그런데 여기서 2번을 이긴 사람은 모두 알고 있다. 즉 1,3,4번은 모두 2번을 이겼기 때문에 당연히 5번도 이길 것이다.

(승 > 패)
4 > 2 > 5 → 4 > 5
3 > 2 > 5 → 3 > 5
1 > 2 > 5 → 1 > 5

이렇게 되면 5번 역시 4명과의 경기 결과를 알 수 있기 때문에 등수가 결정된다.

그렇다면 1번을 분석해보자. INPUT 에는 [1, 2] 값이 있다.

(승 > 패)
1 > 2

2번과 다른 경기의 결과를 살펴보면, 아래와 같다.

(승 > 패)
4 > 2 → 1,4번을 비교할 수 없음
3 > 2 → 1,3번을 비교할 수 없음
2 > 5 → 1 > 5

총 1번의 경우, 총 두 사람간의(두 경기의 결과) 관계만을 명확히 확인할 수 있다. 그래서 결과적으로 1번의 랭킹은 확정지을 수 없다.

이러한 과정을 통해서 결론지을 수 있는 것들이 있다. 첫번째, INPUT을 통한 직접 비교(주어진 두 사람간의 결과)를 통해서 랭킹 관계를 알 수 있다. 두번째, 자신이 경기한 사람이 다른 사람과의 한 경기 결과를 통해서도 랭킹을 알 수 있다. 이 때는 내(A)가 상대(B)를 이겼다면, 상대(B)가 다른 상대(C)를 이긴 경우에만 관계를 알 수 있다. 지는 경우에도 마찬가지이다. 삼자대면이 단방향을 이루어야만 관계를 특정지을 수 있다.

이제 이러한 로직을 어떻게 코드로 표현할지 생각해보자. 일반적을(대부분) 배열을 통해서 표현할 수 있다. 아래와 같은 이미지 속의 배열을 만들자!

이 그림을 그리면서 생각해보니, 사실 랭킹(순위)이라는게 우리가 대진표를 통해서 이를 추론하는 과정이였다는 것을 떠올리게 되었다. 특히 월드컵에서 보면 위와 같은 대진표를 그리지 않는가!

어릴적에 이런 대진표를 그려서 항상 그랬듯,,, 대한민국의 16강 경우의 수를 찾아보곤 했다. 왜 경우의 수를 찾았을까? 아직 순위가 확정되지 않았으니까! 결국 4개의 팀 중에서 3경기의 경기 결과를 나와야만 모든 순위가 확정되는 것이다. 결국 위 문제는 평소에 경험했던, 특히 월드컵때마다... 생각해왔던 로직에 대한 것이였다. 이걸 문제로 접하니 이렇게 어렵게 풀게 되다니...

코드

function solution(n, results) {
  const graph = Array.from({ length: n + 1 }, () =>
    Array.from({ length: n + 1 }, () => 0)
  );

  // 직접 비교를 통한 대진표
  for (let i = 0; i < results.length; i++) {
    const [w, d] = results[i];
    graph[w][d] = 1;
    graph[d][w] = -1;
  }

  // 간접 비교를 통한 대진표
  for (let i = 1; i < graph.length; i++) {
    for (let j = 1; j < graph[i].length; j++) {
      if (graph[i][j]) {
        for (let k = 1; k < graph[j].length; k++) {
          if (graph[i][j] === 1 && graph[j][k] === 1) {
            graph[i][k] = 1;
            graph[k][i] = -1;
          }
          if (graph[i][j] === -1 && graph[j][k] === -1) {
            graph[i][k] = -1;
            graph[k][i] = 1;
          }
        }
      }
    }
  }

  // 최대값 뽑기
  let count = 0;
  for (let i = 1; i < graph.length; i++) {
    if (graph[i].filter(Boolean).length === n - 1) count++;
  }

  return count;
}

결론

• 플로이드 와샬 알고리즘

• 다익스트라 알고리즘 (덤!)

위 문제를 설명할 때, 난 위 알고리즘에 대해서 전혀 생각하지 않고 문제에만 집중해서 이해해보고자 했다. 물론 그 안에 저런 알고리즘이 녹아있을거라고 생각이 들지만 결국 알고리즘도 어떠한 문제를 해결하기 위한 방법이다. 우선은 문제를 정확히 이해하고자 하는 노력이 우선일 것이다.

그래도 어려운 알고리즘이 접목되어있는 문제를 이해할 수 있어서 좋은 시간이였다. 물론 여러가지 힌트를 통했지만 말이다. 문제는 문제이고 위에서 언급한 알고리즘에 대해서도 알아보는 시간을 갖도록 할 것이다. 지식은 다다익선이니까!