[BOJ]21278 - 호석이 두 마리 치킨(G5)

문제 링크

21278-호석이 두 마리 치킨

입력

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

출력

한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.
만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.

문제 풀이

플로이드-와샬 알고리즘을 이용해서 모든 경로의 최단거리를 구해 times 배열에 저장

그 후 selected 라는 배열에 두개의 건물 번호와 최단거리를 저장하는 배열을 만들어
하나씩 확인하면서 갱신

숫자가 크지 않았기때문에 플로이드 와샬이 가능했지만
그렇지 않은 경우에는 bfs 를 이용해야 할 것 같다.

package Algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Code21278 {
    static final int INF = 10000001;
    static int N, M;
    static int[][] times;
    static int[] selected = new int[3];

    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());
        times = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            Arrays.fill(times[i],INF);
            times[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());
            times[u][v] = 1;
            times[v][u] = 1;
        }

        floyd();
        getMin();
        System.out.println(selected[0] + " " + selected[1] + " " + selected[2] * 2);
    }

    static void getMin() {
        for (int i = 0; i < 3; i++) {
            selected[i] = INF;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                int sum = 0;
                for (int k = 1; k <= N; k++) {
                    sum += Math.min(times[i][k], times[j][k]);
                }
                if (sum < selected[2]) {
                    selected[0] = i;
                    selected[1] = j;
                    selected[2] = sum;
                }
            }
        }
    }

    // 모든 최단 경로 구하는 플로이드-와샬 알고리즘
    static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    times[i][j] = Math.min(times[i][k] + times[k][j], times[i][j]);
                }
            }
        }
    }
}