코학다식
[프로그래머스/C++] 순위 본문
프로그래머스: 순위
플로이드 와샬로 모든 정점에서 모든 정점의 관계를 파악해서 풀 수 있는 문제였다. 구체적인 순위가 필요한 것이 아니라 "정확하게 순위를 매길 수 있는 선수의 수"를 구하는 것이 목적이므로, 플로이드 와샬을 이용해서 모든 정점(선수)에서 모든 정점(선수)까지의 경로를 찾는다. 경로가 존재한다면 승패가 가려진 상황이므로, 한 정점에서 다른 모든 정점까지의 경로가 존재하는 경우라면 순위를 정확하게 매길 수 있다. 처음에 배열을 int
로 선언했을 때는 계속 오답이라고 나왔는데, 이유를 모르겠다. 어차피 0이냐, 아니냐만 따지면 되기 때문에 문제될 것이 없다고 생각했는데 왜일까?
풀이
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
bool arr[101][101];
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for(auto r : results) {
arr[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(arr[i][k] && arr[k][j]) {
arr[i][j] = true;
}
}
}
}
for(int i = 1; i <= n; i++){
int cnt = 0;
for(int j = 1; j <= n; j++) {
if(arr[i][j] || arr[j][i]) cnt++;
}
if(cnt == n - 1) answer++;
}
return answer;
}
'Algorithm > Problem' 카테고리의 다른 글
[프로그래머스/C++] 가장 먼 노드 (0) | 2020.09.08 |
---|---|
[프로그래머스/C++] 베스트앨범 (0) | 2020.09.03 |
[프로그래머스/C++] 위장 (0) | 2020.09.02 |
[백준/BOJ/C++] 11657번 :: 타임머신 (0) | 2020.09.01 |
[프로그래머스/C++] 섬 연결하기 (0) | 2020.09.01 |
Comments