🔍 Problem

1389 케빈 베이컨의 6단계 법칙

---

📃 Input&Output

---

🌁 문제 배경

가. 접근 방법
A라는 사람이 있다고 가정해보자, 그렇다면 나머지 B~E까지의 연결고리 수를 구한다. 이것을 A~E까지 다 구하고 가장 작은 사람의 번호를 구하면 될 것이다.

나. 사용할 알고리즘 선택
모든 사람, 즉 모든 노드의 연결고리를 구한다는 것은 각 노드 사이에 최단거리에 대한 정보를 담아둔 표가 필요하다는 것이고 이것은 플로이드 워셜을 의미한다.

---

📒 해결 과정

가. 먼저, 초기 플로이드워셜 DP 매트릭스를 그린다.

나. 각 노드별로 연결된 노드의 최단거리를 더한다.
가로행으로 더해줘서 1차원 배열에 저장하면 된다.

다. 위의 1차원 배열에서 최소값의 인덱스를 구한다.
우선 순위 큐를 사용하여 최소값이 여러개인 경우의 인덱스를 넣어, 최소 인덱스를 peek하였다.

---

💻 Code

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

public class P1389 {
    public static void main(String args[]) throws Exception {
        // 두사람이 최소 몇단계 만에 이어질 수 있는지 계산하는 게임
        // 각 사람마다 최단거리 구해서
        // 그 중에서 제일 작은거 Pick

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N, M;
        int[][] dp;
        int inf = 100000000;
        int[] kevin_arr;
        int min_kevin = 100000000;
        int result_man = 101;
        PriorityQueue<Integer> que;


        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = 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());
            dp[a][b] = 1;
            dp[b][a] = 1;
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                if (dp[i][j] == 0 && i != j) {
                    dp[i][j] = inf;
                }
            }
        }


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

        kevin_arr = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                kevin_arr[i] += dp[i][j];
            }
        }


        que = new PriorityQueue<>();
        // min_kevin = 1000000 (init)
        // result_man = 101 (init)
        for (int i = 1; i <= N; i++) {
            if (min_kevin >= kevin_arr[i]) {
                min_kevin = kevin_arr[i];
            }
        }

        for (int i = 1; i <= N; i++) {
            if (kevin_arr[i] == min_kevin) {
                que.add(i);
            }

        }

        bw.write(que.peek() + "\n");

        bw.flush();
        bw.close();
    }
}

---

🤔 느낀점

푸는 맛이 쏠쏠하다. 우선순위 큐 문법을 좀 외울 필요가 있어 보인다.

PriorityQueue<Integer> que = new PriorityQuere<>();

타입에 <Integer> 쓰는거 까먹지 말자