[SWExpertAcademy]1263번 사람 네트워크2 - Java

문제

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

SW Expert Academy

 

 

풀이

가중치가 있을 때 최단 경로를 구하는 경우 다익스트라 알고리즘을 많이들 사용한다. 근데 가중치가 음수라면 다익스트라 알고리즘을 사용하지 못하는데, 그때 사용할 수 있는 알고리즘이 바로 이 플로이드 와샬 알고리즘이다.

 

얘는 3중 for문을 돌리기 때문에 시간 복잡도는 O(N^3)이 나오지만(다익스트라 알고리즘도 인접 행렬을 이용하면 O(N^3)의 시간 복잡도가 나오기도 함) 구현이 간단해서 사용되는 경우가 적지 않다고 한다. 하지만 시간 복잡도가 이런 만큼 N이 커지게 되면 답이 없기 때문에 사용하지 못한당

 

암튼 얘는 플로이드 와샬 알고리즘으로 푼 코드임!

자세한건 주석으로!

 

 

코드

// 1263 - 사람 네트워크2

package d6;

import java.util.Scanner;

public class Num1263_사람네트워크2 {
    static final int INF = 9999999;
    static int N, adjMatrix[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 1; t <= T; t++) {
            N = sc.nextInt();
            adjMatrix = new int[N][N];
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    adjMatrix[i][j] = sc.nextInt();
                    if (i != j && adjMatrix[i][j] == 0) {// 자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
                        adjMatrix[i][j] = INF;
                    }
                }
            }

            // 출발지-->경유지-->목적지로 3중 루프 돌리면 오답
            // 경유지-->출발지-->목적지로 3중 루프 돌려야 정답
            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; // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 패스
                        }

                        if (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
                            adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                        }
                    }
                }
            }

            int min = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                int sum = 0;
                for (int j = 0; j < N; j++) {
                    sum += adjMatrix[i][j];
                }
                if (sum < min) {
                    min = sum;
                }
            }

            System.out.println("#" + t + " " + min);
        }
    }
}