[프로그래머스] LV.3 순위 (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

풀이

해당 문제는 크게 두 가지 방식으로 풀 수 있다. 하나는 플로이드-와샬 방법으로 풀이하는 법과, 다른 하나는 승리/패배를 각각 따로 구분하여 탐색한 뒤 순위판별 조건을 만족하는 지 검사하는 방법이다. JS에서는 두 가지 방식 모두 정상 통과가 되는 것을 확인했다. 그러나 해당 포스트에서는 플로이드-와샬에 대해 정리할 겸 첫 번째 방법으로 풀이해보고자 한다.

순위를 매길 수 있는 조건이 정확하게 어떠한 경우에 가능한지 먼저 짚고 넘어가야 한다. 현실 세계에 비추어 이해하려고 하면 당연히 이해가 가지 않을 것 이다. 왜냐하면 현실 세계에서는 A라는 선수가 B를 이기고, B라는 선수가 C라는 선수를 이겼음에도 A가 항상 C를 이긴다고 보장할 수 없기 때문이다. 하지만 해당 문제에서는 이러한 합리적 사고를 버리자. 가끔씩 알고리즘 문제를 너무 현실에 대입하여 생각한다면 꽤나 변태적인 문제들을 심심찮게 볼 수 있다.

본론으로 돌아와 A -> B 이고 B -> C 이면, A -> C 라는 것이 보장된다는 것을 문제의 설명에서 파악할 수 있어야 한다. 무언가 명제 문제를 푸는 것 같지만 카테고리는 또 그래프로 분류되어 있으니 아이러니 하다. 확실하게 순위 결정 조건을 정리하면 다음과 같다.

• 선수가 n명일 때 특정 선수의 승/패 합이 n-1인 경우

자기 자신은 이기고 지고 할 수 없기 때문에 승/패의 합이 주어진 n과 같아질 수는 없다. 때문에 우리는 results를 탐색하면서 각 선수들의 승/패 여부를 계산해 줄 것 이다.

먼저 플로이드-와샬 알고리즘에 대한 이해가 필요할 것 같다. 앞에서 플로이드-와샬 알고리즘을 적용해 풀어보자했는데, 이는 과연 무슨 알고리즘일까?

플로이드-와샬 알고리즘은 원래 모든 노드로부터 각각의 노드까지의 최단 거리를 계산하는 알고리즘을 뜻한다. 비슷한 알고리즘으로 역시 널리 알려진 다익스트라 알고리즘이 있는데, 다익스트라 알고리즘의 경우는 한 노드에서 각각의 노드까지의 최단 거리를 계산한다는 점이 다르다.

"아! 그렇다면 플로이드-와샬 알고리즘은 최단 거리를 계산할 때 사용할 수 있겠구나~" 라는 생각이 듦과 동시에 근데 "해당 문제에서 최단 거리를 구해야 하나?" 라는 의문이 동시에 들 수 있다. 정답만 말하자면 최단 거리는 굳이 구할 필요가 없다. 다만 우리는 플로이드-와샬 알고리즘에서 최단 거리를 구하는 그 과정만 필요로 한다. 그렇다면 어떤 방식으로 최단 거리를 구하길래 그 과정을 필요로 하는 것일까?

기본적으로 플로이드-와샬 알고리즘의 내부 로직은 DP(Dynamic Programming)을 기반으로 돌아간다. 총 3번의 반복문을 돌게 되는데, 시작노드(i) - 경유노드(k) - 도착노드(j)의 구조로 최단 거리를 갱신하게 된다. 즉 X라는 노드가 있고 Y라는 노드가 있을 때, X -> Y로 가는 경로까지의 길이가 있을 것이다. 이때 X와 Y사이에 경유할 수 있는 노드 Z가 있는 경우, 기존 X -> Y 와 (X -> Z) + (Z -> Y)의 값 중 더 작은 값을 선택하는 구조라고 보면 된다. 플로이드-와샬 알고리즘에 대한 자세한 설명과 작동 방식은 해당 포스트를 참고하자. 플로이드-와샬 알고리즘의 반복 과정은 아래와 같다.

// 최단 경로를 구하는 플로이드 와샬 알고리즘
// dp 배열 초기화: 보통 n x n 크기의 2차원 배열을 만들어준다.
const dp = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j++) {
    dp[i][j] = original[i][j];
    // 연결된 노드의 정보와 연동해주는 과정이 필요하다.
  }
}

// k = 경유노드, i = 시작노드, j = 도착노드, n = 노드개수
// dp[i][j] = 노드 i 부터 노드 j 까지의 거리
// 기존에 구한 경로 값을 계속 다음 계산에 활용하기 때문에
// dp 기법을 사용하는 것.
for(let k = 0; k < n; k++) {
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      if(dp[i][k] + dp[k][j] < dp[i][j]) {
        dp[i][j] = dp[i][k] + dp[k][j];
      }
    }
  }
}

말로 설명하기 보단 때로 코드로 보는 것이 더욱 이해하기 명쾌할 때가 있다. dp 배열에서 dp[i][j]가 노드 i 로부터 노드 j 까지의 거리라는 점에 유의하면 더욱 이해하기 쉬울 것 이다.

자 그렇다면 다시 원래의 질문으로 돌아와서, 위와 같이 최단 경로를 구하는 과정이 왜 해당 문제에서 필요한 것일까? 다음을 생각해보자.

A라는 선수는 B라는 선수를 항상 이긴다. 또 B라는 선수는 C라는 선수를 항상 이긴다. 이때 우리는 문제 조건에 의해 A가 C 역시 항상 이긴다라는 것을 앞에서 살펴보았다. 그런데 이를 접근하는 과정에 플로이드-와샬 알고리즘과 상당히 닮아있지 않은가? 즉 B라는 선수가 경유 노드가 된다면 다음의 과정이 성립한다. (화살표 및 더하기 기호 등은 일단 신경쓰지 말자. 표현의 편의를 의해 임의로 사용한 기호일 뿐이다)

• (A -> B) + (B -> C) = (A -> C)

즉 A에서 B로 가는 길과 B에서 C로 가는 길이 있다면 A에서 C로 가는 길이 있다. 즉 A 역시 C를 항상 이길 수 있다. 이처럼 경유 노드를 이용하여 승패여부를 판단할 수 있다는 점이 플로이드 와샬 알고리즘과 일치한다. 다만 앞에서 이야기한 바와 같이 우리는 최단 경로를 구할 필요는 없기 때문에 단순히 A가 C를 이긴다라는 정보만 체크할 수 있으면 된다. 때문에 위에서 구현한 플로이드-와샬의 내부 로직을 다음과 같이 수정할 수 있다.

// 여기선 최단 경로가 필요하지 않으므로 false로 초기화를 진행
const dp = new Array(n).fill().map(_ => new Array(n).fill(false));
for(const res of results) {
  // 주어진 승패관계 results를 토대로 dp 배열 초기화
  dp[res[0]-1][res[1]-1] = true;
}

// k는 경유노드로써 가장 외곽에 위치한다. 
// 이 부분이 이해가 가지 않는다면 직접 적어가며
// 내부 로직의 변화를 살펴본다면 왜 k가 가장 외곽에 위치해야 하는지 알 수 있을 것이다.
for(let k = 0; k < n; k++) {
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      // 노드 i에서 경유지 k로 가는 경로와
      // 경유지 k에서 노드 j로 가는 경로가 있다면
      if(dp[i][k] && dp[k][j]) {
        // 노드 i에서 노드 j로 가는 경로도 존재
        // 경로가 존재한다는 것은 곧 승리할 수 있음을 의미
        // 따라서 그냥 true 값을 넣어준다.
        dp[i][j] = true;
      }
    }
  }
}

위의 반복과정을 모두 거치고 나면 dp 배열에는 각 노드에서 그래프에 존재하는 모든 노드들에 대해 승리여부에 대한 정보를 파악할 수 있다. 그렇다면 패배여부는 어떻게 확인할 수 있을까? 앞서 패배여부는 따로 저장해주지 않은 것을 알 수 있다. 그런데 위 과정에서 굳이 승/패 여부를 구분해주지 않아도 상관이 없다. 즉 dp[i][j]가 true라면 dp[j][i]역시 true가 된다. 이는 앞서 정의한 dp의 정의에 따르면 모순이지만 우린 그저 두 개중 하나의 값이 패배라고 생각만 하면 된다. 문제 조건에 의해 모순이 주어지지 않는다고 했기 때문에 이 같은 접근이 가능한 것이다. (이를 굳이 구분하고 싶다면 승리는 1, 패배는 -1 이런 식으로 값을 다루게 주어도 될 것이다. 이 경우 1과 -1일때를 모두 체크하여 횟수를 체크해야 한다.)

따라서 우리는 다시 dp 배열을 돌면서 dp[i][j] 와 d[j][i] 중 하나라도 true 라면 카운트를 증가시키고, 해당 카운트가 n-1과 일치한다면 해당 노드는 순위를 매길 수 있다고 판단하면 된다. 이를 코딩하면 다음과 같다.

for(let i = 0; i < n; i++) {
  let count = 0;  // 승리 및 패배 여부의 횟수 저장할 변수
  for(let j = 0; j < n; j++) {
    // 승리 or 패배 여부가 기록되어 있다면
    if(dp[i][j] || dp[j][i]) count++;
  }
  // 순위 판별 조건 만족 시 선수인원 증가
  if(count === n-1) answer++;
}

해당 문제만 보고 사실 플로이드-와샬 알고리즘을 바로 떠올려서 풀이하기엔 쉽지 않다. 서론에서 이야기 한대로 승리그룹과 패배그룹을 나누어 접근하는 것이 오히려 더 용이할 수도 있다. 하지만 이런 식으로 플로이드 와샬 알고리즘을 적용하여 풀이할 수 있다는 것을 캐치한다면 다른 문제 풀이에도 도움이 되지 않을까 싶다. 아래는 주석을 제외한 전체 코드이다.

코드

function solution(n, results) {
  let answer = 0;
  const dp = new Array(n).fill().map(_ => new Array(n).fill(false));
  
  for(const res of results) {
    dp[res[0]-1][res[1]-1] = true;
  }
  
  for(let k = 0; k < n; k++) {
    for(let i = 0; i < n; i++) {
      for(let j = 0; j < n; j++) {
        if(dp[i][k] && dp[k][j]) {
          dp[i][j] = true;
        }
      }
    }
  }
  
  for(let i = 0; i < n; i++) {
    let count = 0;  
    for(let j = 0; j < n; j++) {
      if(dp[i][j] || dp[j][i]) count++;
    }
    if(count === n-1) answer++;
  }
  
  return answer;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/49191?language=javascript