[ BOJ ][JAVA][21278] 호석이 두 마리 치킨

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

21278번: 호석이 두 마리 치킨

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	433	227	170	50.898%

문제

컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.

이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.

키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.

컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.

입력

첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.

출력

한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.

만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.

제한

• 2 ≤ N ≤ 100
• N-1 ≤ M ≤ N×(N - 1)/2
• 1 ≤ Ai , Bi ≤ N (Ai ≠ Bi)

예제 입력 1

5 4
1 3
4 2
2 5
3 2

예제 출력 1

1 2 6

위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 작은 건물 번호를 출력해야 함을 유의하자.

코드

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

public class p21278 {
    static int n, m, min = Integer.MAX_VALUE;
    static int[][] map;
    static int[][] dist;
    static int[] place;
    static boolean[] visited;
    static int[] minPlace = new int[2];
    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());

        place = new int[2];
        visited = new boolean[n + 1];
        map = new int[n + 1][n + 1];
        // 각 도시간의 거리를 계산하기 위해 초기화
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++) {
                if (i == j) continue;
                map[i][j] = n;
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

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

        // 플로이드 와샬 알고리즘을 통해 최단거리 셋팅
        floyd_warshall();

        solution(1, 0);
        System.out.println(minPlace[0]+" "+minPlace[1]+" "+min);
    }

    static void floyd_warshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }

    static void solution(int start, int depth) {
        if (depth == 2) {
            int sum = 0;
            // 치킨집이 아닌 건물에서 가장 가까운 치킨집까지의 최단거리들을 더하자.
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    int mmin = Integer.MAX_VALUE;
                    for (int j = 0; j < 2; j++) {
                        mmin = Math.min(map[i][place[j]], mmin);
                    }
                    sum += mmin * 2;
                }
            }
            if (min > sum) {
                for (int j = 0; j < 2; j++) {
                    minPlace[j] = place[j];
                }
                min = sum;
            }
            return;
        }

        for (int i = start; i <= n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            place[depth] = i;
            solution(i, depth + 1);
            visited[i] = false;
        }
    }
}

더 간단하게 구현 풀이

import java.util.*;
import java.io.*;
public class Main {

    public static int N, M, adj[][], dist[][];
    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());

        adj = new int[N+1][N+1];
        dist = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a][b] = adj[b][a] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(i==j) continue;

                if(adj[i][j]!=0) dist[i][j] = adj[i][j];
                else dist[i][j] = 1000000;
            }
        }

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

        int ans1 = Integer.MAX_VALUE;
        int ans2 = Integer.MAX_VALUE;
        int sum = Integer.MAX_VALUE;

        for (int i = 1; i <= N; i++) {
            for (int j = i+1; j <= N; j++) {
                int tmp = solve(i, j);
                if(sum > tmp) {
                    ans1 = i; ans2 = j;
                    sum = tmp;
                }
            }
        }

        System.out.printf("%d %d %d", ans1, ans2, sum*2);
    }

    public static int solve(int i, int j) {
        int distance = 0;
        for (int k = 1; k <= N; k++) {
            distance += Math.min(dist[i][k], dist[j][k]);
        }
        return distance;
    }
}