<Algorithm> 104. 1389번 케빈 베이컨의 6단계법칙

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

• BFS와 플로이드 워셜 알고리즘 문제

• 두가지 방법 모두 풀었는데 확실히 플로이드 워셜 알고리즘으로 풀었을때 코드가 간결하다

• 최솟값인 index를  여러개 일때 인덱스가 작은 것을 return 하는 부분에서 어떻게 효율적으로 할지에 대한 고민이 많았다. 

• 생각해보니 아래서 부터 시작하기 때문에 동률일 경우를 판단하지 않으면 그대로 가는 간단한 방법이 있었다..

• Arrays.fill로 new LinkedList()를 돌리면 이상한 값이 들어갔다. 이부분은 유의 해야 할 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static List<Integer>[] friend_list;
    static int n;
    static int m;
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        long start = System.currentTimeMillis();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n+1];
        lvl = new int[n+1];
        Arrays.fill(lvl, 1);
        friend_list = new LinkedList[n+1];
        for(int i = 0; i < n+1; i++) friend_list[i] = new LinkedList<>();
        /******************************
         * BFS를 이용해서 탐색할때 마다 단계를
         * 올려주면서 lvl 값을 구한 뒤 리스트에
         * 저장하고 Sort해서 가장 최소가 되는
         * index를 구한다 
         *******************************/
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(!friend_list[a].contains(b)&&!friend_list[b].contains(a)) {
                friend_list[a].add(b);
                friend_list[b].add(a);
            }
        }
        
        List<People> ans = new LinkedList<>();
        
        for(int i = 1; i < n+1;i++) {
            sum = 0;
            
            for(int j = 1; j < n+1; j++) {
                if(i==j) continue;
                visited = new boolean[n+1];
                Arrays.fill(lvl, 1);
                bfs(i, j);
            }
            ans.add(new People(i, sum));
        }
        Collections.sort(ans);
        System.out.println(ans.get(0).num);
        long end = System.currentTimeMillis();
        System.out.println(end-start+"ms");
    }
    
    static int lvl[];
    static int sum = 0;
    public static void bfs(int target, int friend) {
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        
        while(!queue.isEmpty()) {
            int idx = queue.remove();
            visited[idx] = true;
            for(Integer in : friend_list[idx]) {
                if(!visited[in]) {
                    if(in == friend) {
                        sum += lvl[idx];
                        return;
                    }else {
                        queue.add(in);
                        lvl[in] = lvl[idx]+1;
                        //System.out.println(lvl[in]);
                    }
                }
            }
        }
        
    }
    static class People implements Comparable<People>{
        int num;
        int sum;
        
        public People(int num, int sum) {
            super();
            this.num = num;
            this.sum = sum;
        }
 
        @Override
        public int compareTo(People other) {
            if(sum == other.sum) {
                return num - other.num;
            }
            return sum - other.sum;
        }
    }
}
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main2 {
    static int n;
    static int m;
    static boolean visited[];
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        //long start = System.currentTimeMillis();
        /******************************
         * 플로이드 워셜 알고리즘을 이용해서 
         * 각각의 최단거리를 구한 뒤
         * 최단거리의 합을 이용해서
         * 가장 최소가 되는 index를 구한다 
         *******************************/
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int arr[][] = new int[n+1][n+1];
        for(int i = 1; i < n+1;i++) {
            Arrays.fill(arr[i], 999999);
        }
        
        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;
        }
            
        for(int k = 1; k < n+1; k++) {
            for(int i = 1; i < n+1; i++) {
                for(int j = 1; j < n+1; j++) {
                   if(i==j) continue;
                   if(arr[i][j] > arr[i][k] + arr[k][j]) {
                       arr[i][j] = arr[i][k] + arr[k][j];
                   }
                }
            }
        }
        int idx = 0;
        for(int i = 1; i < n+1; i++) {
            int sum = 0;
            for(int j = 1; j < n+1; j++) {
                if(i == j) continue;
                sum += arr[i][j];
            }
            if(sum < min) {
                min = sum;
                idx = i;
            }
        }
        System.out.println(idx);
        //long end = System.currentTimeMillis();
        //System.out.println(end-start+"ms");
    }    
}
 

참고 & 출처