[BOJ][ZOAC 2019]18243번 - Small World Network

한양대학교 ERICA 알고리즘 연구학회 영과일의 내부 대회 "ZOAC 2019"의 문제 출제 및 검수를 맡게 되었습니다.

 

그중 F번 문제인 Small World Network에 대한 풀이입니다.

 

 

 

목표

문제 화면 캡쳐

2019-2학기 김태형교수님의 "소셜 네트워크 분석"이라는 수업을 들으면서 배웠던 내용을 문제로 만들어 보았습니다. Small World Network란 이론에서 실제 실험 값의 평균이 6에 수렴하더라 라는 수업 내용을 듣고 친구 관계 네트워크가 주어졌을 때 이 네트워크가 Small World Network가 만족하는지 확인하는 문제입니다.

 

이 문제를 해결하기 위한 조건은 이렇습니다.

• 모든 노드들에 대해서 한 노드에서 어떤 노드로 가는 방법이 6단계 이하여야 한다.

즉 1~N까지 모든 노드들을 탐색하면서 해당 노드와 다른 모든 노드들이 6단계 이하로 연결되어 있어야 한다는 것입니다.

 

저는 이 문제를 BFS를 통해 해결하였지만 플로이드-워샬 알고리즘을 통해서도 해결할 수 있습니다.

 

이 문제의 시간 복잡도는 O(모든 노드(N) * BFS(N)) == O(N²) 입니다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

vector <vector<int> > node(101); // 노드의 개수

int chk[101];

void bfs(int n){ // BFS 따로 BFS에 대해선 설명하지 않겠습니다.
    int fn;
    queue <int> q;
    chk[n] = 0;
    q.push(n);
    while(!q.empty()){
        fn = q.front();
        q.pop();
        for(int i = 0; i < node[fn].size(); i++){
            if(chk[node[fn][i]] == -1){
                q.push(node[fn][i]);
                chk[node[fn][i]] = chk[fn] + 1;
            }
        }
    }
}

int main(){
    int N, K; cin >> N >> K;
    for(int i = 0; i < K; i++){ // 친구관계 형성
        int a, b; scanf("%d%d", &a, &b);
        node[a].push_back(b);
        node[b].push_back(a);
    }
    for(int i = 1; i <= N; i++){
        memset(chk, -1, sizeof(chk)); // 노드를 탐색할 때 마다 노드 초기화
        bfs(i); // BFS
        for(int j = 1; j <= N; j++){
            if(chk[j] == -1 || chk[j] > 6){ // 노드가 이어져있지 않거나, 6보다 많은 단계로 연결되어 있으면
                printf("Big World!\n");
                return 0;
            }
        }
    }
    printf("Small World!\n");
}

---