Treejin's Note

문제 설명

• 유저 수(N), 친구 관계 수(M)이 주어짐
• M개의 친구 관계가 주어짐(중복 O)
• 모든 유저 수와 연결했을 때, 그 간선의 합의 값이 가장 작은 사람을 출력하기

문제 풀이

이 문제는 최단거리를 구하는 문제이다.

그래프에서 최단거리는 다익스트라, 프림, 플로이드-와샬 등의 다양한 풀이 방법이 있다.

다익스트라, 프림은 한 정점에 대한 최단거리를 구하는 솔루션이라면, 플로이드-와샬은 모든 정점에 대한 최단거리를 구하는 솔루션이다.

이 문제에서는 모든 간선 사이의 최단 거리를 구하고, 그 핪의 최소값을 찾는 문제이므로 플로이드-와샬 방법을 사용했다.

플로이드 와샬은 다음과 같은 방식으로 수행한다.

1. 모든 간선에 대한 정보를 인접 행렬 형태로 표현한다.
   1. 기본값은 매우 큰 값으로 설정한다.
   2. 자기 자신 - 자기 자신을 나타내는 위치는 0으로 설정한다.(자신에서 자신으로 가는 길을 최단거리로 설정)
2. i정점부터 j정점으로 가는 최소 거리를 계산한다.
   1. 이때, i에서 특정 정점 k 를 거쳐 j로 가는 경우와, i에서 j로 바로 가는 경우를 비교해 더 작은 값으로 선택한다.

시간복잡도 : O(N^3)

시간복잡도가 큰 방식이므로 정점의 개수가 적을 때만 사용가능한 방법이다.

문제 풀이 코드

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

public class _1389_케빈베이컨의6단계법칙 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] friends = new int[N + 1][N + 1];
	
		for (int i = 0; i <= N; ++i) {
			Arrays.fill(friends[i], 99999999);	//초기값 설정
			friends[i][i] = 0;					//자신-자신은 0으로 설정
		}

		for (int i = 0; i < M; ++i) {	//간선 정보 입력
			st = new StringTokenizer(in.readLine());
			int person1 = Integer.parseInt(st.nextToken());
			int person2 = Integer.parseInt(st.nextToken());
			friends[person1][person2] = 1;
			friends[person2][person1] = 1;
		}

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

		//최소값 구하기
		int min = Integer.MAX_VALUE;
		int person = 0;
		for(int i = 1; i<=N;++i) {
			int sum = 0;
			for(int j = 1; j<=N;++j) {
				sum += friends[i][j];
			}
			if(min > sum) {
				person = i;
				min = sum;
			}
		}
		
		System.out.println(person);
	}

}