백준 No.18243 Small World Network - JAVA

문제

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

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

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

예를 들어 이 문제를 김모씨(23)와 이지은님(27)이 서로 생판 모르는 관계라도 최대 6단계만 거치면 서로 연결이 도어있다는 것이다.

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

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

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

 

 

입력

첫번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어지낟. 모든 사람은 1부터 N까지 번호가 매겨져있다.

두 번째 줄부터 K+1번째 줄까지 친구 관계를 나타내는 AB가 한 줄에 하나씩 주어진다. 

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

 

5 5
1 2
2 3
3 5
1 4
1 3

 

풀이

플로이드 와샬을 이용해 전체에 INF(큰값)을 먼저 다 때려넣고, 주어진 값들 위치에만 1을 부여한다.

그리고 해당 알고리즘을 사용해 작은 값을 계속 때려넣고, 다 때려넣은 배열을 뒤져서 INF 값( 자기 자신은 INF이므로 i != j 도 추가로 필요)이 없는 경우와 6을 넘어선 경우가 없다면 Small World가 맞고, 아니면 Big World이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {


    static  int INF = Integer.MAX_VALUE/2;
    static int N,M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

         N = Integer.parseInt(st.nextToken());
         M = Integer.parseInt(st.nextToken());



        int map[][] = new int[N+1][N+1];
        for (int i = 0; i < N+1 ; i++) {
            Arrays.fill(map[i],INF);
        }
        for (int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[a][b] = map[b][a] = 1;
        }



        for (int i = 1; i < N+1 ; i++) {
            for (int j = 1; j < N+1 ; j++) {
                for (int k = 1; k < N+1 ; k++) {
                    map[j][k] = Math.min(map[j][i]+map[i][k],map[j][k]);
                }
            }
        }

        output(map);
    }

    static void output(int map[][]){
        for (int i = 1; i < N+1 ; i++) {
            for (int j = 1; j < N+1; j++) {
                if((map[i][j] == INF && i != j) || map[i][j] > 6) {
                    System.out.println("Big World!");
                    return;
                }
            }
        }

        System.out.println("Small World!");
    }
}