#2458번 키 순서 (C++)

링크 : www.acmicpc.net/problem/2458

2458번: 키 순서

 

이 문제는 플로이드 와샬 알고리즘을 활용했다. 

 

문제의 풀이는 다음과 같다. 

(1) 배열을 만든다. 이때 모든 노드들은 갈 수 없다고 먼저 선정해준다 (임의의 최대값 INF를 설정하여 값을 삽입)

(2) 같은 노드에서 같은 노드로 가는 배열은 0으로 초기화한다 (ex: v[1][1])

(3) 배열의 값을 입력받고 채워준다. 

(4) floydwarshall DFS를 실행한다. 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100000
using namespace std;
int n = 0, m = 0, ans = 0;
int v[501][501]; //학생들의 정보
int d[501][501]; //플로이드와샬 결과

void floydwarshall(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            d[i][j] = v[i][j]; //값을 복사해준다
        }
    }

    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(d[i][j]>d[i][k]+d[k][j]&&d[i][j]==INF) d[i][j] = 1;
            }
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = 0, b = 0;
    cin >> n >> m;
    fill(&v[0][0],&v[n][n],INF); // 모든 지점은 갈 수 없다고 설정
    for(int i=1; i<=n; i++){
        v[i][i] = 0; // 자기자신은 0으로 초기화
    }
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a][b] = 1; // a에서 b로 갈 수 있다고 설정
    }

    floydwarshall();

    for(int i=1; i<=n; i++){
        int start = 0, stop = 0;
        for(int j=1; j<=n; j++){
            if(d[i][j]==1) start++;
            if(d[j][i]==1) stop ++;
        }
        if(start+stop == n-1) ans ++;
    }
    cout << ans << "\n";
    return 0;
}