백준 2219 - 보안 시스템 설치

문제

https://www.acmicpc.net/problem/2219

리뷰

플로이드-워셜로 풀이할 수 있는 간단한 문제였다.

문제에서 요구하는 것은 모든 정점까지 이동하는데 드는 비용이 가장 최소인
정점 i를 구하는 것이다.

따라서, 플로이드-워셜을 통해 모든 정점간 최단 경로 비용을 구하고,
특정 정점 i에서 다른 정점까지 이동하는 비용의 합을 구하여, 그 합이
최소가 되는 정점을 구하는 형태로 로직을 구성하였다.
이 때, 답을 여러 개일 수 있기 때문에 우선 답이 되는 정점들을 List에 담고
정렬하여 답이 될 수 있는 정점중 번호가 가장 작은 것을 구할 수 있도록
구현하였다.

로직의 시간복잡도는 플로이드-워셜의 $O(N^3)$으로 수렴하고 이는 $N=200$인
최악의 경우에도 2초의 제한 조건을 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        map = new int[N + 1][N + 1];
        for (int i = 1; i < map.length; i++)
            for (int j = 1; j < map[i].length; j++) {
                if (i == j) continue;

                map[i][j] = MAX_VALUE;
            }

        int i, j, c;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            i = parseInt(st.nextToken());
            j = parseInt(st.nextToken());
            c = parseInt(st.nextToken());

            map[i][j] = Math.min(map[i][j], c);
            map[j][i] = Math.min(map[j][i], c);
        }

        floyd();
        List<Integer> ans = getAnswer();
        System.out.println(ans.get(0));
        br.close();
    }

    static List<Integer> getAnswer() {
        int minDistSum = MAX_VALUE;
        List<Integer> answer = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= N; j++)
                sum += map[i][j];

            if (sum > minDistSum)
                continue;

            if (sum == minDistSum) {
                answer.add(i);
                continue;
            }

            minDistSum = sum;
            answer.clear();
            answer.add(i);
        }

        Collections.sort(answer);
        return answer;
    }

    static void floyd() {
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }

}

결과