Life Engineering
[프로그래머스] 순위 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/49191
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool floyd[101][101]={false,};
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for (auto r : results)
floyd[r[0]][r[1]]=true;
for (int k=1; k<=n; k++){
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
if (floyd[i][k] && floyd[k][j])
floyd[i][j]=true;
}
}
}
for (int i=1; i<=n; i++){
int cnt=0;
for (int j=1; j<=n; j++){
if (floyd[i][j] || floyd[j][i]){
cnt++;
}
}
if (cnt==n-1)
answer++;
}
return answer;
}
개인적으로 아이디어를 떠올리기 어려운 문제였다.
floyd warshall 알고리즘을 이용해서, 승패를 가를 수 있는 경우를 따져주는게 포인트다.
a가 b를 이기면 floyd[a][b]=true, b가 c를 이기면 floyd[b][c]=true 이다.
이때 floyd-warshall 알고리즘을 이용해서 floyd[a][c]를 따져줄 때, floyd[a][b], floyd[b][c] (즉 b를 거치는 케이스) 가 모두 true이면 a가 c를 이긴다는 것이 성립되기 때문에 승패를 가를 수 있으므로, floyd[a][c]=true 해준다.
이런 식으로 모든 case에 대해 따져준 뒤, 한 명씩 체크해서 승패를 가를 수 있는 경우가 n-1가지이면(본인과 대결하는 경우는 빼준다), 순위를 가를 수 있는 애이므로 +1 해준다.
이때 승패를 가를 수 있는 경우를 체크할 때 floyd[i][j] 외에도, floyd[j][i] 가 true인지도 같이 체크해주는 것이 중요하다.
자기 외에 다른 모든 사람에 대해 승패를 가를 수 있는 경우일 때, 순위를 따질 수 있는 것이다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 예상 대진표 (C++) (0) | 2021.11.11 |
---|---|
[프로그래머스] N개의 최소공배수 (C++) (0) | 2021.11.11 |
[프로그래머스] 순위 검색 (C++) (0) | 2021.11.04 |
[BOJ 15654] N과 M(5) (C++) (0) | 2021.10.28 |
[프로그래머스] 프린터 (C++) (0) | 2021.10.27 |