[백준_18243번] Small World Network

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

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의 친구 관계는 중복되어 입력되지 않는다.

 

[코드]

import java.util.*;

public class BaekJoon_18243 {
	static int n,k;
	static final int INF=(int)1e9;
	static int[][] graph;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		
		graph=new int[n+1][n+1];
		
		// 그래프 초기화
		for(int i=0;i<=n;i++)
			Arrays.fill(graph[i],INF);
		
		// 이어져 있는 노드는 거리를 1로 변경
		for(int i=0;i<k;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			// 양방향
			graph[a][b]=graph[b][a]=1;
		}
		
		// 플로이드 워셜 알고리즘
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					graph[i][j]=Math.min(graph[i][j],graph[i][k]+graph[k][j]);
		
		// 결과 출력
		if(network()==true)
			System.out.println("Small World!");
		else
			System.out.println("Big World!");
	}
	
	/*
	 * 플로이드 워셜 알고리즘을 통해 각 배열에는 다른 노드로 가는 최소 비용이 저장되어 있다.
	 * 이때 배열의 값이 6이 넘어 Small World 조건을 만족하지 않는 경우와,
	 * 자기 자신으로 가는(i==j) 경우가 아닌데 배열의 값이 INF라면 
	 * 모든 네트워크는 연결되어 있지 않은 상태이기 때문에 Small World가 될 수 없다.
	 */
	static boolean network() {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if((graph[i][j]==INF&&i!=j)||graph[i][j]>6) {
					return false;
				}
			}
		}
		return true;
	}
}

 

[고찰]

 이번 문제는 최단거리를 구하는 문제인 것을 보고 다익스트라와 플로이드 워셜 중 어떤 알고리즘을 써야할까 고민했다. 문제를 읽어보니 각 노드에서 다른 모든 노드로 가는 최단거리를 구해야 하기 때문에 플로이드 워셜 알고리즘을 사용하여 최단거리를 구했다. 

 Small World가 될 수 없는 경우는 두 가지가 있는데 첫 번째는 주어진 조건처럼 다른 노드로 가는 최단거리가 6 이상인 경우가 있는 것이고, 두 번째는 자기 자신으로 가는 경우 이외에도 배열의 값이 INF라면 모든 네트워크가 연결되어 있지 않다는 의미이기 때문에 해당 경우 또한 Small World가 될 수 없다. 이 두 경우가 존재한다면 Big World를 출력해준다.