programmers.co.kr/learn/courses/30/lessons/49191?language=cpp#
코딩테스트 연습 - 순위
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
programmers.co.kr
결과적으로 플로이드 와샬 알고리즘을 사용하면 풀리는 문제였다.
그렇다면 왜 플로이드 와샬 알고리즘을 사용하면 되는 것일까?
아래의 표는 문제의 테스트 케이스를 플로이드 와샬 알고리즘을 사용한 후의 dist 배열을 출력한 것이다.
| 0 | 1 | INF | INF | 1 |
| -1 | 0 | -1 | -1 | 1 |
| INF | 1 | 0 | -1 | 1 |
| INF | 1 | 1 | 0 | 1 |
| -1 | -1 | -1 | -1 | 0 |
플로이드 와샬 알고리즘은 반복문을 돌면서 모든 지점을 비교하여 최단거리가 갱신되는데,
이때, 순위가 확실하게 이기거나 지는 상황이 아니라면 값이 갱신되지 못한다.
따라서 논리적으로 순위가 불분명해지는 경우는 INF값으로 남게 되므로
각 행에서 다른 정점으로 INF값이 있는 경우 두 선수의 우위를 판단하지 못한 것이므로
INF가 하나도 없는 행의 개수가 정답이 된다.
코드
'Algorithm' 카테고리의 다른 글
| 백준 - 2146번(다리 만들기) / C++ (0) | 2021.02.27 |
|---|---|
| 백준 - 16947번(서울 지하철 2호선) / C++ (1) | 2021.02.26 |
| 백준 - 1422번(숫자의 신) / C++ (0) | 2021.02.22 |
| 프로그래머스 - 가장 큰 수 / C++ (0) | 2021.02.22 |
| 프로그래머스 - Summer/Winter Coding(2019)(멀쩡한 사각형) / C++ (0) | 2020.10.28 |