[완탐] 호석이 두 마리 치킨 - java

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

---

<풀이 방법>

1. 각 건물에서 건물 까지의 거리를 구해놓고

2. 어떤 건물에 치킨집을 차릴 지 조합을 구한다.

3. 건물에서 치킨집 사이의 거리를 구하는데 더 가까운 곳으로 계산한다.

---

각 건물 사이의 거리 구하기

여기서는 '플로이드-워셜' 을 사용하였다.

n 은 0 ~ 100인 만큼 100^3 해도 100만으로 제한시간 안에 계산이 가능하다.

'플로이드-워셜' 에서의 중요한 점은

3중 for문의 가장 바깥 for문이 '거쳐가는 노드' 인덱스여야 한다는 것.

그렇지 않으면 최신화된 정보를 통해 갱신하는것이 아니라 뒤죽박죽이 됨.

---

<정답 코드>

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb;
    static StringTokenizer st;

    static int n, m, min = Integer.MAX_VALUE, resultX, resultY;
    static int[] chicken;
    static int[][] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n+1][n+1];
        visited = new boolean[n+1];
        chicken = new int[2];

        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1 ; j <= n ; j ++) {
                arr[i][j] = Integer.MAX_VALUE;
                if (i == j) arr[i][j] = 0;
            }
        }

        for (int i = 0 ; i < m ; i ++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            arr[from][to] = 1;
            arr[to][from] = 1;
        }

        floyd();

        dfs(0, 1);

        System.out.println(resultX + " " + resultY + " " + min * 2);

    }

    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 (arr[i][k] == Integer.MAX_VALUE || arr[k][j] == Integer.MAX_VALUE) continue;
                    if (arr[i][j] > arr[i][k] + arr[j][k]) {
                        arr[i][j] = arr[i][k] + arr[j][k];
                    }
                }
            }
        }
    }

    static void dfs(int depth, int idx) {
        if (depth == 2) {
            int sum = 0;
            int x = -1;
            int y = -1;

            for (int i = 1 ; i <= n ; i ++) {
                // 치킨집 사이의 거리가 짧은것을 선택해서 합연산 하기
                sum += Math.min(arr[i][chicken[0]], arr[i][chicken[1]]);
            }

            if (min > sum) {
                resultX = chicken[0];
                resultY = chicken[1];
                min = sum;
            }

            return;
        }

        for (int i = idx ; i <= n ; i ++) {
            if (!visited[i]) {
                visited[i] = true;
                chicken[depth] = i;
                dfs(depth + 1, i);
                visited[i] = false;
            }
        }
    }
}