[백준 2458] 키 순서 (C++)

문제 출처 : https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, cnt = 0;
    cin >> n >> m;
    int arr[501][501] = { 0 };
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        arr[a][b] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) arr[i][j] = 1;
        }
    }
    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] == 1 && arr[k][j] == 1) arr[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = max(arr[i][j], arr[j][i]);
            arr[j][i] = max(arr[i][j], arr[j][i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 0) break;
            if (j == n) cnt++;
        }
    }
    cout << cnt;
    return 0;
}

알고리즘

- 그래프 이론

- 그래프 탐색

- 플로이드-워셜

 

키 순서를 알기 위해서는 자기보다 큰 사람이 누구인지, 작은 사람이 누구인지 모두 알고 있어야 한다.

자기 자신과는 키 비교를 안해도 순서를 알 수 있기 때문에 1로 체크해준다.

키를 비교한 결과 a < b 를 입력받고 arr[a][b] = 1로 체크해준다.

플로이드-워셜 알고리즘을 돌려주면 자기보다 큰 사람이 체크 된다.

배열을 돌며 반대의 경우도 체크하여 자기보다 작은 사람을 체크해준다.

배열을 돌며 0이 하나라도 있다면 비교 불가이므로 넘어간다.

모두 1이라면 비교 가능이므로 cnt를 1 올려준다.

 

플로이드-워셜 알고리즘 이후 작은 사람을 체크 하는 이유

체크 후에 돌리게 된다면 예제와 같은 경우 3 -> 4 -> 5로 3과 5가 이어지게 되어 오답이 나온다.

플로이드-워셜 이후 체크를 한다면 3 -> 4, 4 -> 3, 5 -> 4, 4 -> 5로만 이어지고 3과 5는 이어지지 않아 정답이 제대로 나온다.