[Programmers] 순위

문제 : https://programmers.co.kr/learn/courses/30/lessons/49191

---

A가 B를 이겼는데 B가 C를 이겼다면 A가 C를 이긴것과 같다.

어디선가 많이 본 것 같은..

A에서 B로 가는 최단거리가 x1이고, B에서 C로 가는 최단거리가 x2라면 A에서 C로 가는 거리의 최단거리 중 하나가 x1 + x2 일 수 있다.

플로이드 워셜 알고리즘의 기본 이론이다. 

알고리즘이론 글을 안쓴지 오래되었는데 다익스트라랑 벨만포드는 포스팅했는데 플로이드는 없네.

그렇지만 최단거리 알고리즘 중에 제일 좋아하는 알고리즘이다. (구현이 간단해서 ㅎㅎ)

플로이드 워셜을 돌려서 승부결과를 nxn 크기의 matches 배열에 채운다.

matches[A][B] = A가 B를 이겼으면 true. 아니거나 알 수 없으면 false.

이 배열로 i 번째 선수의 등수를 알 수 있는 경우는 어떻게 판단할 수 있을까.

조건에서 모순인 경우는 존재하지 않는다고 하니. A가 B를 이겼으면 B가 A를 이기는 경우는 matches 배열에 세팅되지 않았을 것이다.

만약 i번째 선수를 이기는 선수들의 합과 i번째 선수에게 진 선수(= i번째 선수가 이긴 선수)들의 합이 n-1이라면(자기자신 제외) i번째 선수의 순위를 결정지을 수 있다.

따라서 matches[j][i] + matches[i][j] (j는 0~n) == n-1 인 i의 갯수를 구하면 정답이된다.

cf) c++ 기준 true = 1, false = 0.

 

시간복잡도는 O(N^3).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Graph/%EC%88%9C%EC%9C%84.cpp