백준 27039 - Sweet Butter

문제

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

리뷰

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

$P$개의 목초지중 소들이 머무는 $N$개의 목초지가 있고, 각 소들의 목초지에서
가장 작은 총 비용으로 도달할 수 있는 목초지를 찾는 것이 문제의 조건이었다.

이를 구하기 위해 소들이 머무는 목초지들의 정보를 cows에 저장하고,
플로이드 워셜을 통해 모든 목초지간의 최단 경로 비용 정보를 도출한 후
한 목초지를 선택하고 해당 목초지까지 소들이 도달하는데 필요한 총 비용을
구하는 과정을 반복하며 최소 총 비용을 도출해 답을 구했다.
(로직에서 답을 출력하기 직전 이중 for문 부분)

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

아마 1억=1초가 아닌 더 널널한(10억=1초 정도..) 제한 조건을 설정되어
플로이드-워셜로도 풀이가 가능한 것 같다. 최악의 경우 $P^3=800^3$은
약 5억정도의 수치라 1억=1초 조건하에서는 시간 제한을 통과하지 못하는 것이 맞다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int P;
    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());
        int N = parseInt(st.nextToken());
        P = parseInt(st.nextToken());
        int C = parseInt(st.nextToken());

        map = new int[P + 1][P + 1];

        List<Integer> cows = new ArrayList<>();
        for (int i = 0; i < N; i++)
            cows.add(parseInt(br.readLine()));

        int u, v, w;
        for (int i = 1; i < map.length; i++)
            for (int j = 1; j < map.length; j++) {
                if (i == j) continue;

                map[i][j] = MAX_VALUE;
            }

        while (C-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            map[u][v] = map[v][u] = w;
        }

        floyd();

        int minTotal = MAX_VALUE;
        int total;
        Loop1:
        for (int i = 1; i <= P; i++) {
            total = 0;

            for (Integer cow : cows) {
                if (map[cow][i] == MAX_VALUE)
                    continue Loop1;

                total += map[cow][i];
            }

            minTotal = Math.min(minTotal, total);
        }

        System.out.println(minTotal);
    }

    static void floyd() {
        for (int k = 1; k <= P; k++)
            for (int i = 1; i <= P; i++)
                for (int j = 1; j <= P; 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]);
                }
    }
}

결과