백준 1389번
https://www.acmicpc.net/problem/1389

---

문제

---

생각하기

---

• 각 노드별로 최단 거리를 구하면 되는 문제이다.

• 플로이드 워셜과 다익스트라 2가지로 구현했다.

동작

다익스트라로 푸는게 익숙해서 다익스트라인 BFS로 설명하자면,

각 친구인 노드 별로 모든 노드로가는 최단 거리를 구하면 된다.

1번 친구 기준이면, 다른 친구까지의 최단 거리를 구해서 거리를 저장해놓고 해당 거리의 모든 합을 저장해둔 다음

2, 3, 4.. 순으로 계속 각자 친구까지의 거리를 구해서 모두 합을 구한뒤 가장 작은 값을 가지는 node를 정답으로 출력하면 된다.

결과

---

코드

---

플로이드 워셜

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

public class Main {

    // input
    private static BufferedReader br;

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

    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 ans = -1;
        int min = INF;
        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += arr[i][j];
            }

            if (min > sum) {
                min = sum;
                ans = i;
            }
        }

        sb.append(ans);
        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 (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++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    continue;
                }
                arr[i][j] = INF;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a][b] = 1;
            arr[b][a] = 1;
        }
    } // End of input()
} // End of Main class

다익스트라

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE / 4;
    private static int N, M, ans, min;
    private static List<List<Node>> adjList;

    private static class Node implements Comparable<Node> {
        int node;
        int dist;

        public Node(int node, int dist) {
            this.node = node;
            this.dist = dist;
        } // End of Node()

        @Override
        public int compareTo(Node o) {
            return dist = o.dist;
        } // End of compareTo()
    } // End of Node 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++) {
            dijkstra(i);
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void dijkstra(int start) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pque = new PriorityQueue<>();
        pque.offer(new Node(start, 0));

        while (!pque.isEmpty()) {
            Node now = pque.poll();

            for (Node next : adjList.get(now.node)) {
                if (dist[next.node] > dist[now.node] + next.dist) {
                    dist[next.node] = dist[now.node] + next.dist;
                    pque.offer(new Node(next.node, dist[next.node]));
                }
            }
        }

        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += dist[i];
        }

        if (min > sum) {
            min = sum;
            ans = start;
        }
    } // End of dijkstra()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        min = 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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adjList.get(a).add(new Node(b, 1));
            adjList.get(b).add(new Node(a, 1));
        }
    } // End of input()
} // End of Main class