18243 Small World Network

문제 링크

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

풀이

전형적인 플로이드-와샬 문제였당
친구 관계가 있는 경우 cost를 1, 없으면 큰 값을 주고 플로이드-와샬을 통해 모든 정점으로부터 모든 정점까지의 거리의 최소값을 구한다. 만약 정점과 정점 사이의 거리가 6 이상이 되는 경우가 있다면 Big World!를 출력하고 그렇지 않다면 Small World!를 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, K;
int INF = 10000;
int arr[101][101];

void floydWarshall(){
    int d[101][101];
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(arr[i][j] == 0){d[i][j] = INF; continue;}
            d[i][j] = arr[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][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(d[i][j] > 6 || d[i][j] == INF){
                cout<<"Big World!"<<endl;
                return;
            }
        }
    }
    
    cout<<"Small World!"<<endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>K;
    
    for(int i=0; i<K; i++){
        int A, B;
        cin>>A>>B;
        arr[A][B] = arr[B][A] = 1;
    }
    
    floydWarshall();
    
    return 0;
}