아이디어

• "최소 개수의 회선만을 복구, 모든 노드 연결" -> 이미 연결된 노드를 다시 연결하지 않는다.
  • 즉, 사이클을 순회하지 말라는 뜻이다.
• "다른 컴퓨터와의 통신에 필요한 시간 평균 최소" -> 모든 노드의 최단거리(시간) 합이 최소
  • 자신과의 거리는 0이므로 자신을 포함시켜도 상관 없다.
• 모든 두 점 간의 최단거리를 계산한 뒤, 모든 도착점에 대한 최단거리 합이 최소가 되는 출발점을 찾으면 된다.
• 플로이드-워셜 알고리즘을 구현하기만 하면 된다.

코드

import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, ans;
	static int dist[][];
	
	static int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		// init
		dist = new int[N+1][N+1];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				dist[i][j] = (i == j) ? 0 : INF;
			}
		}
		
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			int A = Integer.parseInt(tk.nextToken());
			int B = Integer.parseInt(tk.nextToken());
			int C = Integer.parseInt(tk.nextToken());
			dist[A][B] = dist[B][A] = C;
		}
		
		// floyd-warshall
		for (int k=1; k<=N; k++) {
			for (int i=1; i<=N; i++) {
				for (int j=1; j<=N; j++) {
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
		
		int minSum = INF;
		for (int a=1; a<=N; a++) {
			int sum = 0;
			for (int b=1; b<=N; b++) {
				sum += dist[a][b];
			}
			if (sum < minSum) {
				minSum = sum;
				ans = a;
			}
		}
		
		System.out.println(ans);
	}
}

메모리와 시간

• 메모리: 19320 KB
• 시간: 312 ms

리뷰

• 1번 조건에 낚여 한참 헤맸던 문제