(C++) - 백준(BOJ) 2458번 : 키 순서

https://www.acmicpc.net/problem/2458

2458번: 키 순서

floyd warshell 응용 문제였습니다.

 

풀이방법

 간선을 i정점 - j정점으로 표현합니다.

 

 1. 정점 u, v를 m만큼 입력받습니다. 이 정보는 이차원 배열 adj에 가는 경로가 있음을 표현하기 위해 1로 저장됩니다.

 

 2. 입력 후에 바로 가는 경로외에 다른 정점을 거쳐 목적지 정점에 도착할 수 있는지 확인하며 정보를 저장합니다. i - k, k - j 가 연결이 되어있다면 i - j로도 갈 수 있다는 의미입니다. 따라서 입력받은 간선을 제외하고도 해당 조건에 의해 i에서 j로 갈 수 있다면 1로 없다면 0으로 설정해줍니다.

 

 3. 모든 정점 i, j를 확인하며 i - j로 연결된 차수들을 세주어 배열 degree변수에 저장합니다. i - j가 1이라면 i정점에 연결된 정보++, j정점에 연결된 정보++의 식으로 세줍니다.

 

 4. 세준 차수가 n -1이라면 다른 이들과의 모든 연결점이 있으므로 자신의 키 정보를 알 수 있습니다. 따라서 ans를 ++해주고 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int adj[501][501], degree[501];
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(adj[i][k] && adj[k][j]) 
                    adj[i][j] = 1;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(adj[i][j]) degree[i]++, degree[j]++;

    for(int i = 1; i <= n; i++) 
        if(degree[i] == n - 1) ans++;
        
    cout << ans << '\n';
}