[백준] S1 18243번 Small World Network (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

18243번: Small World Network

[문제] 

작은 세상 네트워크(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!"를 출력한다.

 

---

[풀이]

1. 값들을 입력받기 전에 배열을 범위보다 큰 값으로 초기화를 해준다.

2. 배열을 채워준다.

3. 플루이드 와샬을 사용한다.

4. 배열을 탐색하면 6보다 큰 값이 있다면 플래그를 true로 적용해준다.

5. 플래그값이 true라면 Big World를, 아니라면 Small World를 출력한다.

[접근]

1. 플루이드 와샬로 문제를 풀면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {
	static int max = 10000;
	static boolean check;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[n][n];
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (i != j)
					arr[i][j] = max; // 배열을 max 값으로 갱신
			}
		}
		
		for (int i = 0; i < k; i++) { 
			st = new StringTokenizer(br.readLine());
			
            // 0부터 시작을 위해 -1
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			
			arr[a][b] = arr[b][a] = 1;
		}
		
		// 플루이드 와샬
		for (int t = 0; t < arr.length; t++) { // 경유지
			for (int i = 0; i < arr.length; i++) { // 출발지
				if (i == t) // 경유지 == 출발지면 탐색 불필요
					continue;
				
				for (int j = 0; j < arr.length; j++) { // 도착지
					// 경유지 == 도착지 or 출발지 == 도착지면 탐색 불필요
					if (i == j || t == j)
						continue;
					
					// 경유지를 거치는 경우 vs 바로 가는 경우 더 적은 것
					arr[i][j] = Math.min(arr[i][j], arr[i][t] + arr[t][j]);
				}
			}
		}
		
		// 결과 탐색
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				// 6번만에 도착이 되는지 탐색을 하는 것이므로 6보다 큰지 체크
				if (arr[i][j] > 6) {
					check = true; // 큰 세상
					break;
				}
			}
			
			if (check)
				break;
		}
		
		// 큰 세상이면 Big World! 출력
		if (check)
			System.out.println("Big World!");
		// 아니면 Small World 출력
		else
			System.out.println("Small World!");
	}
}