백준 21278 - 호석이 두 마리 치킨

문제

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

리뷰

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

로직 설명
우선 플로이드-워셜에 사용할 2차원 배열 map 을 int 최대값으로 초기화해준다.
(자기 자신에 대한 경로 제외, map[i][j]=0) 이후 간선 정보를 입력받으며
map[i][j]의 값을 갱신해준다.

모든 입력을 받은 후에는 플로이드 워셜 로직을 통하여 모든 정점간 최단 경로 비용을
도출하고 getBuildingNumber 로직을 통해 문제 조건에 맞는 건물 번호 조합을
구하였다.

getBuildingNumber 로직은 모든 도시에서 왕복 시간이 가장 적은 치킨집을 차릴
두 도시의 조합을 구하며, 도시 조합을 표현하기 위해 Pair라는 두 도시 번호를
필드로 가지는 클래스를 정의하였다. 가능한 도시 조합별 왕복 시간 합을 구하는
과정에서 최소 왕복 시간 합을 구하기 위하여 minDistSum이라는 변수를
Integer.MAX_VALUE로 초기화하여 놓았다.

한편, 최소 왕복 시간 합을 구하는 도시 조합이 여러 개 있을 수 있기 때문에
로직의 반환 형태는 일단 List<Pair> 형태로 규정하였고, 삼중 for문에서는
두 개의 도시(i,j)에 치킨집을 차렸을 때 각 도시(k)에서의 왕복 비용
(sum)을 구하고 이 값이 최소 왕복 비용과 같을 때는 answer에 해당 조합을
추가해주고, 이외에 경우는 minDistSum과 answer를 갱신해주는 방식으로
답이 될 수 있는 조합 리스트를 구한다.

이후 문제 조건에 따라 조합내에서 번호가 작은 순으로 answer를 정렬하여
최종적인 답을 도출한다.

시간 복잡도
전체 로직의 시간 복잡도는 플로이드-워셜의 $O(N^3)$으로 수렴하며 이는
$N=100$인 최악의 경우에도 무난히 제한 조건 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.*;

public class Main {
    static int N, M;
    static int[][] map;
    static int minDistSum = MAX_VALUE;

    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());
        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;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            i = parseInt(st.nextToken());
            j = parseInt(st.nextToken());
            map[i][j] = map[j][i] = 1;
        }

        floyd();
        List<Pair> buildingNumber = getBuildingNumber();
        Pair pair = buildingNumber.get(0);
        int n1 = Math.min(pair.i, pair.j);
        int n2 = Math.max(pair.i, pair.j);
        System.out.println(n1 + " " + n2 + " " + minDistSum);
        br.close();

    }

    static List<Pair> getBuildingNumber() {
        minDistSum = MAX_VALUE;

        int sum = 0;
        List<Pair> answer = new ArrayList<>();

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

                for (int k = 1; k <= N; k++) {
                    sum += Math.min(map[i][k] + map[k][i], map[j][k] + map[k][j]);
                }

                if (sum > minDistSum) continue;


                if (sum == minDistSum) {
                    answer.add(new Pair(i, j));
                } else {
                    answer.clear();
                    minDistSum = sum;
                    answer.add(new Pair(i, j));
                }
            }
        }

        answer.sort((p1, p2) -> {
            int n1 = Math.min(p1.i, p1.j);
            int n2 = Math.min(p2.i, p2.j);

            if (n1 == n2) {
                return compare(Math.max(p1.i, p1.j), Math.max(p2.i, p2.j));
            }

            return compare(n1, n2);
        });

        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]);
                }
    }

    static class Pair {
        int i, j;

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

결과