백준 18243번 Small World Network [C++]

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

 

 

 

#문제 간단 정리

플로이드 워셜을 사용하자

 

#문제 해결 방법

 

모든 간선에서에 간선까지의 거리를 찾아야되니까 플로이드 워셜을 사용하자

 

그런데 n 이 작으므로 n^2 이상을 사용하는 bfs 를 사용해도 된다.

 

플로이드 워셜 코드

https://dfdfg42.tistory.com/entry/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-C%EC%BD%94%EB%93%9C

플로이드 워셜 C++코드

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

void floydWarshall(vector<vector<int>>& dist, int N) {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<vector<int>> dist(N, vector<int>(N, INF));

    // 자기 자신으로의 거리는 0으로 초기화
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < K; i++) {
        int A, B;
        cin >> A >> B;
        A--; // 0-based index
        B--; // 0-based index
        dist[A][B] = 1;
        dist[B][A] = 1;
    }

    floydWarshall(dist, N);

    bool flag = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dist[i][j] > 6) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
    }

    if (flag) {
        cout << "Small World!" << '\n';
    }
    else {
        cout << "Big World!" << '\n';
    }

    return 0;
}