[SWEA] 1263. 사람 네트워크2 D6 - Floyed Warshall

[SWEA] 1263. 사람 네트워크2 D6 - Floyed Warshall

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN

Input

맨 위의 줄에는 전체 테스트 케이스의 수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄에 주어지며, 사람 수인 양의 정수 N이 주어진 다음, 사람 네트워크의 인접 행렬이 행 우선 (row-by-row) 순으로 주어진다.

단, 각 숫자 사이에는 1개의 공백이 주어진다.

Output

총 T줄에 T개의 테스트 케이스 각각에 대한 답을 한 줄에 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 사람 그래프에서 사람들의 CC 값들 중에서 최솟값을 한 줄에 출력한다.

Constraints

입력으로 주어지는 사람 네트워크에서 노드 자신을 연결하는 간선은 없다.

또한 사람 네트워크는 하나의 연결 요소(connected component)로 구성되어 있다.

단, 사람 네트워크의 최대 사용자 수는 1,000 이하이다.

테스트 케이스들은 아래의 그룹들로 이루어져 있다.

그룹 1 싸이클이 없고 N <= 10 인 경우
그룹 2 싸이클이 없고 10 < N <= 100 인경우
그룹 3 싸이클이 있고 N<= 10
그룹 4 싸이클이 있고10 < N <= 100
그룹 5 모든 경우가 존재하고 100 < N <= 1000

Example

input

20
5 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0
5 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0
...

output

#1 4
#2 5
…

Solution & Inpression

플루이드 워샬 알고리즘을 이용하여 해결하였다.

Code

언어 : JAVA

메모리 : 120,644 kb

실행시간 : 3,686 ms

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D6_1263_사람네트워크2.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            int N = sc.nextInt();
            int[][] matrix = new int[N][N];
            int INF = 987654321;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    if (i != j && tmp == 0)
                        matrix[i][j] = INF;
                    else
                        matrix[i][j] = tmp;
                }
            }

            for (int k = 0; k < N; k++) {
                for (int i = 0; i < N; i++) {
                    if (k == i)
                        continue;
                    for (int j = 0; j < N; j++) {
                        if (j == k || i == k)
                            continue;
                        if ((matrix[i][k] + matrix[k][j]) < matrix[i][j])
                            matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
            int min = INF;
            for (int i = 0; i < N; i++) {
                int sum = 0;
                for (int j = 0; j < N; j++) {
                    sum += matrix[i][j];
                }
                if (sum < min) {
                    min = sum;
                }
            }
            System.out.println(min);
        }
    }
}