아이디어

• 문제가 어렵게 쓰여있는데, 결국 i에서 j로 가는 경로의 길이를 D[i][j]라 하면 모든 j에 대한 D[i][j]의 합 중 최솟값을 구하라는 문제이다.
• BFS를 써도 되고, 모든 가중치가 1인 그래프로 생각해 Floyd-Warshall 알고리즘을 써도 된다.
  • 당연히 BFS 쪽이 더 시간복잡도가 좋다.
• BFS의 경우 모든 i를 시작점으로 BFS를 하는데, 각 정점에 도달할 때마다 그때까지의 거리를 누적합한 것이 그 i에 대한 CC값이 된다.
• Floyd-Warshall의 경우 입력값을 변형할 필요가 있다.
  • 연결되지 않은 경우 중 $i \ne j$라면 가중치가 $\infty$인 경우로 생각해야 한다.
  • 최단거리 배열 D[i][j]를 구하고 모든 i에 대해 cc값인 D[j]의 합을 구해 그 중 최솟값을 출력하면 된다.

코드

BFS를 사용한 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	static int T, N, min;
	static ArrayList<ArrayList<Integer>> adjList;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			// 맨 앞 N
			N = Integer.parseInt(st.nextToken());
			// 인접행렬
			adjList = new ArrayList<>();
			for (int i=0; i<N; i++) {
				adjList.add(new ArrayList<>());
			}
			
			for (int i=0; i<N; i++) {		// 행
				for (int j=0; j<N; j++) {	// 열
					int n = Integer.parseInt(st.nextToken());
					if (n == 1) adjList.get(i).add(j);
				}
			}

			min = Integer.MAX_VALUE;
			// 각 정점(사람) 별로 각자 최단경로를 구해서 min 갱신 
			for (int i=0; i<N; i++) {
				bfs(i);
			}
			
			sb.append("#").append(t).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}
	
	static void bfs(int V) {
		Queue<Node> queue = new ArrayDeque<>();
		boolean[] visit = new boolean[N];
		
		visit[V] = true;
		queue.offer(new Node(V, 0));
		
		int dist = 0;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			// node.v <- adjList.get(node.v)
			for (int v: adjList.get(node.v)) {
				if (visit[v]) continue;
				dist += node.cnt + 1;
				if (dist >= min) return;	// 가지치기
				
				visit[v] = true;
				queue.offer(new Node(v, node.cnt + 1));
			}
		}
		
		min = Math.min(min, dist);
	}
	
	static class Node {
		int v, cnt;
		Node(int v, int cnt) {
			this.v = v;
			this.cnt= cnt;
		}
	}
}

Floyd-Warshall 풀이

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

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

	static int INF = Integer.MAX_VALUE / 2;
	
	static int T, N, cc, ans;
	static int[][] D;

	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t = 1; t <= T; t++) {
			tk = new StringTokenizer(rd.readLine());
			N = Integer.parseInt(tk.nextToken());
			
			D = new int[N][N];
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {
					D[i][j] = tk.nextToken().charAt(0) == '1' ? 1 : (i == j) ? 0 : INF;
				}
			}
			
			// floyd-warshall
			for (int k=0; k<N; k++) {
				for (int i=0; i<N; i++) {
					for (int j=0; j<N; j++) {
						D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]);
					}
				}
			}
			
			ans = INF;
			for (int i=0; i<N; i++) {
				cc = 0;
				for (int j=0; j<N; j++) {
					cc += D[i][j];
				}
				ans = Math.min(ans, cc);
			}

			sb.append('#').append(t).append(' ').append(ans).append('\n');
		}
		System.out.println(sb);
	}
}

리뷰

• 한동안 BFS를 안 했더니 까먹을 뻔했다.