(백준) 호석이 두 마리 치킨 - 21278 [JAVA]

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

21278번: 호석이 두 마리 치킨

 

🐢 해설

먼저 빌딩과 도로가 존재하고 양방향이며 도로의 비용이 1로 고정되어 있으므로 해당 간선과 정점을 가지고 각 빌딩에 대해서 다른 모든 빌딩에 대한 거리 최소 비용을 구해야한다.

 

이후 구한 거리값을 가지고 어디에 치킨집을 차렸을 때(2개로 고정) 모든 빌딩의 왕복 합이 낮은지 구하면 된다.

 

특정 빌딩이 아니라 모든 빌딩에 대해 최소 거리값을 구해야 하므로 플로이드 와샬을 사용해서 거리 비용을 구한다. 플로이드와샬의 시간복잡도는 N^3인데 총 100개의 정점이 존재할 수 있으므로 최대 100만번의 비교가 발생하므로 시간복잡도는 충분하다.

 

거리비용 배열을 이용해서 이제 N개의 빌딩에 대해 2개의 치킨집을 차리는 순서가 없는 경우를 모두 뽑는것으로 nC2를 구하면된다. 이는 최대 100 * 99 / 2 = 4950번의 경우의 수가 발생한다.

 

총 시간복잡도는 5000 + 100만번으로 O(N^3)이다.

 

왕복의 거리를 구할 때는 왕복이 가능하므로 치킨집이 없는 i번 빌딩에서 치킨집 빌딩 중 가장 짧은 거리값 * 2이 최소 왕복 비용이다. 이 왕복 비용을 모든 빌딩들에 대해서 더하고, 총 합을 최소로 갖도록 갱신하면 된다.

 

탐색은 순차적으로 이뤄지므로 따로 건물의 번호에 대해서는 비교할 필요없이 갱신만 해주면된다.

🐢 코드

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

public class Main {
    static final int INF = 10000001;
    static int N, M, Min = INF, I, J;
    static int[][] time;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        time = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(time[i], INF);
            time[i][i] = 0;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            time[u][v] = 1;
            time[v][u] = 1;
        }

        floyd();

        // nC2
        boolean[] visited = new boolean[N + 1];
        int[] selected = new int[2];
        Arrays.fill(visited, false);
        comb(1, 0, 2, visited, selected);

        System.out.println(I + " " + J + " " + Min);
    }

    private static void comb(int start, int select, int max, boolean[] visited, int[] selected) {
        if (select == max) {

            int sum = 0;
            for (int i = 1; i < N + 1; i++) {
               if (visited[i]) continue;
                int min = INF;
                for (int k : selected)
                    min = Math.min(time[i][k], min);
                sum += min * 2;
            }

            if (Min > sum) {
                Min = sum;
                I = selected[0];
                J = selected[1];
            }
            return;
        }

        for (int i = start; i < N + 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                selected[select] = i;
                comb(i + 1, select + 1, max, visited, selected);
                visited[i] = false;
            }
        }
    }

    private 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 (time[i][j] > time[i][k] + time[k][j]) {
                        time[i][j] = time[i][k] + time[k][j];
                    }
                }
            }
        }
    }
}