백준 2458) 키순서 골드 4 C++

 

풀이: 플로이드 알고리즘을 x -> y로 가는 커지는 bigDp와 y - x로 가는 smallDp

 

두개를 만들어서 하나는 큰 방향을 따라가고 하나는 작은 방향을 따라간다 

 

왜냐하면 i 보다 큰 j 의 갯수는 bigDp[i][j...]의 방문한 경우이고 i보다 작은 j의 갯수는 smallDp[i][j...]을 방문한 경우이다

 

GLOBMAX가 아니라면 방문한 것이기 때문에 최단경로에 휘둘릴 필요 없이 그냥 방문을 했냐 안했냐 이것이 중요하다

 

i보다 큰 j의 갯수 + i보다 작은 j의 갯수 = n - 1 이 되어야 한다 -1은 자신을 제외한 것이다. 

 

위의 조건이 성립한다면 순서를 i의 키 순서를 알 수 있는 것이 된다.

 

#include <iostream>
#include <vector>

#define GLOBMAX 100000000

using namespace std;

int main() {
    int n, m;

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    vector<vector<int> > bigDp(n + 1, vector<int>(n + 1, GLOBMAX));
    vector<vector<int> > smallDp(n + 1, vector<int>(n + 1, GLOBMAX));

    for (int i = 1; i <= n; i++) {
        bigDp[i][i] = 0;
        smallDp[i][i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int x, y;

        cin >> x >> y;

        bigDp[x][y] = 1;
        smallDp[y][x] = 1;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                bigDp[i][j] = min(bigDp[i][j], bigDp[i][k] + bigDp[k][j]);

                smallDp[i][j] = min(smallDp[i][j], smallDp[i][k] + smallDp[k][j]);
            }
        }
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            bigDp[i][j] = min(bigDp[i][j], smallDp[i][j]);
        }
    }

    int c = 0;

    for (int i = 1; i <= n; i++) {
        int xs = 0;
        for (int j = 1; j <= n; j++) {
            if (bigDp[i][j] == GLOBMAX) {
                continue;
            }
            xs++;
        }
        if (xs == n) {
            c++;
        }
    }

    cout << c;
}