작은 세상 네트워크

작은 세상 네트워크(Small World Network)는 Milgram 교수가 1967년에 처음 밝혀낸 이론이다.

간단히 말하면 전체 네트워크가 거대하더라도 전체가 서로 가깝게 연결될 수 있다는 이론이다.

이 이론에서 Milgram 교수는 지구에 있는 모든 사람이 최대 6단계로 연결될 수 있다고 주장했다.

예를 들어 이 문제를 만든 김 모 씨(23)와 이지은 님(27)이 서로 전혀 모르는 사이여도 최대 6단계만 거치면 서로 연결되어 있다는 것이다.

위 그림에서 정점은 사람, 간선은 친구 관계라 할 때 왼쪽 그래프의 모든 정점은 서로 6단계 이하로 연결되어 있으므로 작은 세상 네트워크를 만족한다. 그러나 오른쪽 그래프의 초록색 정점끼리는 7단계를 거쳐야 연결되므로 작은 세상 네트워크를 만족하지 않는다.

이 이론에 의문이 생긴 김 모 씨는 정말 최대 6단계만 거치면 지구상의 모든 사람이 서로 연결될 수 있는지 확인하고 싶었다.

김 모 씨를 위해 지구상의 모든 사람의 친구 관계가 주어졌을 때 작은 세상 네트워크를 실제로 만족하는지 확인하는 프로그램을 만들어보자.

첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2)

두 번째 줄부터 K+1번째 줄까지 친구 관계를 나타내는 A B가 한 줄에 하나씩 주어진다. (1 ≤ A, B ≤ N)

A와 B가 친구면 B와 A도 친구다. 자기 자신과 친구인 경우는 없다. A와 B의 친구 관계는 중복되어 입력되지 않는다.

해당 네트워크가 작은 세상 네트워크를 만족하면 "Small World!"를, 만족하지 않는다면 "Big World!"를 출력한다.