플로이드-워셜
-
[프로그래머스] 순위알고리즘/프로그래머스 2021. 9. 16. 12:46
문제 링크 풀이 이 문제는 모든 정점에 대해 최단 경로를 찾는 플로이드-워셜 알고리즘을 이용해 풀 수 있습니다. 주어진 예제를 통해 이 알고리즘을 어떻게 적용하는지 알아보겠습니다. 주어진 예제는 {4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5} 입니다. {A, B}에서 A는 B를 항상 이깁니다 - 2는 네 번의 경기를 하므로 순위가 확정적으로 정해집니다 - 5번이 2번에게 확실하게 지는 거라면, 5번은 2번을 이기는 모든 선수에게도 집니다 - {4,2} {2,5}에서 {4,5}가 도출됩니다 - 그러므로 {4, 5}, {3, 5}, {1, 5}, {2, 5}가 성립합니다 코드 #include #include using namespace std; int solution(int n, vec..