[C++]백준(BOJ) - 2548 키 순서(플로이드-와샬)

 

난이도 : 골IV

알고리즘 유형 : 플로이드-와샬, dfs

풀이 방법 : 3중 for문(플로이드-와샬)

 

문제 링크

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

 

문제의 예시

자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산

-> 모든 방법을 탐색한다.

 

a에서 b로 화살표를 그려서 표현하였다.

-> 방향 그래프이다.

 

N (2 ≤ N ≤ 500) 인것을 보아 단순 계산을 한다면 O(N^3)으로 풀 수 있습니다.

또한, 이 문제는 모든 방법을 탐색해야 하므로 플로이드-와샬을 이용하면 됩니다.

 

기본적인 min 연산을 하는 플로이드-와샬과 달리 이 문제는 비교를 하는 문제입니다.

그렇기 때문에 방향 그래프로 경로가 있을때만 플로이드로 체크만 해주면 됩니다.

 

플로이드 연산이 완료되면 방향 그래프이기 때문에 하나만

비교한다면 답이 틀릴 수 있습니다.

 

그래서 [i][j], [j][i] 를 동시에 비교(양방향 체크)해서 연결됨을 확인하고,

n - 1(모두 연결된 정점의 거리) 만큼 연결되어있다면,

모두 연결되었음이 확인된 것이기 때문에 카운팅을 시켜주면 끝입니다.  

 

아래는 코드입니다.

#include <iostream>

using namespace std;

int adj[502][502];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b; cin >> a >> b;
        adj[a][b] = 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;
    
    int answer = 0;

    for (int i = 1; n >= i; i++)
    {
        int cnt = 0;

        for (int j = 1; n >= j; j++)
        {
            if (adj[i][j] || adj[j][i])
                cnt++;
        }

        if (n - 1 == cnt)
            answer++;
    }

    cout << answer;

    return 0;
}