[SWEA] SW expert academy 1263번 사람 네트워크2 자바 풀이 ( 다익스트라, 플로이드-워셜 알고리즘)

sw expert academy 1263번 사람 네트워크2 자바(java) 풀이

• 난이도 : D6
• sw expert academy 1263번 사람 네트워크2
  
  
  

문제정리

1. Closeness Centrality(CC) : 네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가?
2. 사용자 i의 CC(i)는 다음과 같이 계산한다.
   모든 dist(i,j)의 합 (단 dist(i,j)는 노드 i로부터 노드 j까지의 최단 거리)
3. N은 1000 이하이다.
4. 사람들의 CC 값중 최소값을 출력하여라.
   
   
   

문제 풀이

모든 노드에서의 최단 경로를 구하여야 합니다. 즉 All pairs shortest path problem이 됩니다
이는 플로이드-워셜 알고리즘을 이용하여 구할 수 있습니다.

1. 플로이드 워셜 알고리즘

한 정점에서 모든 정점으로 가는 최단 경로를 구합니다. O(n^3) 알고리즘 이지만 코드가 간단하기 때문에 때에따라 잘 쓰면 좋습니다.
3중 for 문만을 이용하면 구할 수 있습니다.
첫번째 for문은 중간에 거쳐가는 정점
두번째 for문은 시작 정점
세번째 for문은 도착 정점을 관리 합니다.
1번 정점에서 3번 정점으로 갈때 다른 정점을 거쳐서 가는 것이 더 빠를 수 있습니다. 이런 경우를 찾아서 업데이트 해줍니다.

예를 들어 1번 정점에서 다른 정점으로 가는 최단 경로가 다음과 같이 구해집니다.
그러므로 CC(i)는 다음과 같이 모두 더하여 구할 수 있습니다.

0 1 1 2 2
1->1 : 없음
1->2 : 1이 최단거리
1->3 : 1이 최단거리
1->4 : 2가 최단거리
1->5 : 2가 최단거리
=> 0 + 1 + 1 + 2 + 2 = 6

모든 점에 대해서 합을 구하고, 그 중에서 제일 작은 값을 구하면 됩니다.

2. 다익스트라 알고리즘

플로이드 워셜은 모든 점에 대해서 구하지만 다익스트라는 한 점에 대해서 다른 점 까지의 최단 거리를 구할 수 있습니다.
즉 이 알고리즘을 모든 점에 대하여 적용하면 모든 점에서 다른 점들에 대한 최단거리 들을 구할 수 있습니다.
다익스트라 알고리즘을 n번 수행하여 나온 값들 중 제일 작은 값을 구하면 됩니다.

swea 사람 네트워크2 플로이드 워셜 알고리즘 자바 코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	class Solution {
	static int n;
	static int[][] dist;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	StringTokenizer st = null;
	for(int tc=1; tc<=T; tc++) {
	st = new StringTokenizer(br.readLine(), " ");
	n = Integer.parseInt(st.nextToken());
	dist = new int[n][n]; // 거리 저장
	for(int i=0; i<n; i++){
	for(int j=0; j<n; j++){
	dist[i][j] = Integer.parseInt(st.nextToken());
	if(i!=j && dist[i][j] == 0) dist[i][j] = 999999; // 주 대각선이 아닌데 0인 경우
	}
	}
	floydWarshall();
	int min = Integer.MAX_VALUE;
	for(int i=0; i<n; i++){
	int ret = 0;
	for(int j=0; j<n; j++)
	ret += dist[i][j];
	min = Math.min(min, ret);
	}
	System.out.println("#" + tc + " " + min);
	}
	}
	private static void floydWarshall(){
	for(int k=0; k<n; k++){
	for(int i=0; i<n; i++){
	if(i == k) continue;
	for(int j=0; j<n; j++){
	if(i == j || k == j) continue;
	// 바로 가는 것 보다 k를 거쳐서 가는게 더 빠른 경우 update
	if(dist[i][k] + dist[k][j] < dist[i][j])
	dist[i][j] = dist[i][k] + dist[k][j];
	}
	}
	}
	}
	}

view raw swea1263_1.java hosted with ❤ by GitHub

swea 사람 네트워크2 다익스트라 알고리즘 자바 코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	class Solution {
	static int n;
	static int[][] adj;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	StringTokenizer st = null;
	for(int tc=1; tc<=T; tc++) {
	st = new StringTokenizer(br.readLine(), " ");
	n = Integer.parseInt(st.nextToken());
	adj = new int[n][n]; // 거리 저장
	for(int i=0; i<n; i++){
	for(int j=0; j<n; j++){
	adj[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	int min = Integer.MAX_VALUE;
	// 모든 점에 대해서 구한다.
	for(int i=0; i<n; i++){
	int sum = djikstra(i);
	min = min > sum ? sum : min;
	}
	System.out.println("#" + tc + " " + min);
	}
	}
	private static int djikstra(int x){
	boolean[] visited;
	int[] distance;
	visited = new boolean[n];
	distance = new int[n];
	// ditance 초기화
	for(int i=0; i<n; i++)
	distance[i] = Integer.MAX_VALUE;
	// 시작점 초기화
	distance[x] = 0;
	visited[x] = true;
	// 시작점과 연결된 노드 distance 갱신
	for(int i=0; i<n; i++){
	if(adj[x][i] != 0 && !visited[i])
	distance[i] = adj[x][i];
	}
	// 모든 점에 대해서
	for(int a=0; a<n-1; a++){
	int min = Integer.MAX_VALUE;
	int minPos = -1;
	// 방문하지 않은 노드 중 최소 값 찾기
	for(int i=0; i<n; i++){
	if(!visited[i] && distance[i] != Integer.MAX_VALUE){
	if(distance[i] < min){
	min = distance[i];
	minPos = i;
	}
	}
	}
	visited[minPos] = true;
	// mixX와 연결 되면서 방문하지 않은 노드들 check
	for(int i=0; i<n; i++){
	if(adj[minPos][i] != 0 && !visited[i]){
	if(distance[i] > distance[minPos] + adj[minPos][i])
	distance[i] = distance[minPos] + adj[minPos][i];
	}
	}
	}
	int sum = 0;
	for(int i=0; i<n; i++)
	sum += distance[i];
	return sum;
	}
	}

view raw swea1263_2.java hosted with ❤ by GitHub