백준 21278번 호석이 두 마리 치킨 Java

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

문제

---

생각하기

---

• 그래프 문제이다.

• 다익스트라

• 플로이드 워셜

• 부르트 포스, 조합

동작

결과

코드

---

Java

다익스트라

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, minDist, num1, num2;
    private static List<List<Edge>> adjList;
    private static final int INF = Integer.MAX_VALUE;

    private static class Edge implements Comparable<Edge> {
        int num;
        int time;

        private Edge(int num, int time) {
            this.num = num;
            this.time = time;
        }

        @Override
        public int compareTo(Edge o) {
            return time - o.time;
        }
    } // End of Edge class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                BFS(i, j);
            }
        }


        sb.append(num1).append(' ').append(num2).append(' ').append(minDist);
        return sb.toString();
    } // End of solve()

    private static void BFS(int start1, int start2) {
        PriorityQueue<Edge> que = new PriorityQueue<>();
        boolean[] isVisited = new boolean[N + 1];
        int[] dists = new int[N + 1];
        Arrays.fill(dists, INF);

        que.offer(new Edge(start1, 0));
        que.offer(new Edge(start2, 0));
        dists[start1] = 0;
        dists[start2] = 0;

        while (!que.isEmpty()) {
            Edge cur = que.poll();

            if (isVisited[cur.num]) continue;
            if (cur.time > dists[cur.num]) continue;
            isVisited[cur.num] = true;

            for (Edge next : adjList.get(cur.num)) {
                if (dists[next.num] > dists[cur.num] + next.time) {
                    dists[next.num] = dists[cur.num] + next.time;
                    que.offer(new Edge(next.num, dists[next.num]));
                }
            }
        }

        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += dists[i];
            if ((sum * 2) >= minDist) {
                return;
            }
        }

        if (minDist > sum * 2) {
            minDist = sum * 2;
            num1 = start1;
            num2 = start2;
        }
    } // End of BFS()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        minDist = INF;

        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adjList.get(u).add(new Edge(v, 1));
            adjList.get(v).add(new Edge(u, 1));
        }
    } // End of input()
} // End of Main class

플로이드 워셜

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[][] arr;
    private static final int INF = Integer.MAX_VALUE / 2;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        floyd();
        int minDist = INF;
        int num1 = 0;
        int num2 = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                int sum = 0;
                kLoop:
                for (int k = 1; k <= N; k++) {
                    if (k == i || k == j) continue;
                    sum += Math.min(arr[i][k], arr[j][k]);
                    if (minDist <= sum * 2) {
                        break kLoop;
                    }
                }

                if (minDist > sum * 2) {
                    minDist = sum * 2;
                    num1 = i;
                    num2 = j;
                }
            }
        }

        sb.append(num1).append(' ').append(num2).append(' ').append(minDist);
        return sb.toString();
    } // End of solve()

    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 (i == j) continue;

                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
    } // End of floyd()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

            arr[u][v] = 1;
            arr[v][u] = 1;
        }
    } // End of input()
} // End of Main Class