[백준, 자바, 1389번] 케빈 베이컨의 6단계 법칙

풀이

• 해당 문제는 단순히 데이터 추가 후
• 결과를 찾고자는 곳에 가장 마지막 유저를 제외하고
• BFS로 찾으며, 조건에 따라 mtx에 단계를 변경하는 것으로 해결
• 내가 작성한 풀이에서 아쉬운 점은 예를 들어 N=5의 경우
• 1번은 모든 사람에 대한 조사를 하기에
• 2,3,4,5번의 모든 1번 mtx가 채워져 있기에
• 2번은 2번은 같으니 제외하고
• 3번부터 5번까지만 찾도록 하고 싶은데
• 이를 어떻게 해결할 수 있을지를 고민해도
• 잘 떠오르지 않아 그냥 마지막 사람을 제외한 모든 사람을 BFS로 탐색하는 것으로 해결...

import java.io.*;
import java.util.*;
public class _1389 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] mtx;
    static List<Set<Integer>> relationArr = new ArrayList<>();
    static StringTokenizer st;
    static int[] result;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        mtx = new int[N+1][N+1];
        result = new int[]{-1,-1};
        addData(N,M);
        findResult(N);
        System.out.println(result[0]);
    }

    private static void addData(int N, int M) throws IOException {
        for (int i=0; i<=N; i++) relationArr.add(new HashSet<>());
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            relationArr.get(a).add(b);
            relationArr.get(b).add(a);
        }
    }

    private static void findResult(int N) {
        for (int i=1; i<=N; i++) {
            if (i!=N) BFS(i,N);
            int hap = 0;
            for (int j=1; j<=N; j++) hap+=mtx[i][j];
            if (result[0]==-1 || result[1]>hap) {
                result[0]=i;
                result[1]=hap;
            }
        }
    }

    private static void BFS(int a, int N) {
        Deque<int[]> dq = new ArrayDeque<>(Arrays.asList(new int[]{a,0}));
        boolean[] visit = new boolean[N+1];
        visit[a]=true;

        while (!dq.isEmpty()) {
            int[] now = dq.pollFirst();
            for (int next: new ArrayList<>(relationArr.get(now[0]))) {
                if (!visit[next]) {
                    dq.add(new int[]{next,now[1]+1});
                    visit[next]=true;
                    if (mtx[a][next]==0) {
                        mtx[a][next]=now[1]+1;
                        mtx[next][a]=now[1]+1;
                    }
                }
            }
        }
    }
}