백준 2458번 : 키 순서

문제 링크 : https://www.acmicpc.net/problem/2458

2458번: 키 순서

 문제 설명 

 

1. 학생의수와 두학생의 키를 비교한 수 가 주어짐.

2. 자신의 키가 몇번째인지 알 수있는 학생의 수를 출력

 

 

 알고 리즘 

 

1. 키를 비교한 경우를 배열로 입력 받는다.

2. arr[i][j] 에서 i번째 학생이 j번째 학생보다 크면 1 작으면 -1 을입력하고

3. 플로이드 알고리즘을통해 arr[i][j] = 0 (누가 큰지모름) 일때, arr[i][k]+arr[j][k] ==2 이면은 arr[i][j] =1 

  arr[i][k]+arr[j][k]== -2 이면은 -1을 대입한다.

  (1 이나 0 이나 -1 인경우 키의 크기를 비교할수없다.)

4.플로이드 알고리즘으로 완성된 배열에서 각 열에서 0이 존재하지 않는다면 cnt ++ 후 마지막에 cnt 출력

 

 코드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N, M;
    int arr[505][505];
    cin >> N >> M;
 
    //배열 초기화
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            arr[i][j] = 0;
        }
    }
 
    for (int i = 0; i < M; i++) {
        int a,b;
        cin >> a >> b;
        arr[a][b] = 1;
        arr[b][a] = -1;
    }
 
    for (int k = 1; k <= N; k++) {
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                if (arr[i][j]!=0)continue;
                
                if (arr[i][k] + arr[k][j] == 2) {
                    arr[i][j] = 1;
                }
                else if (arr[i][k] + arr[k][j] == -2)
                    arr[i][j] = -1;
 
                else
                    arr[i][j] = 0;
            }
        }
    }
 
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        bool pos = true;
        for (int j= 1; j <= N; j++) {
            if (i == j)continue;
            if (!arr[i][j])pos = false;
        }
        if (pos)cnt++;
    }
    cout << cnt;
}