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

 

 

문제가 엄청긴데 요약하자면 그래프에서 A에서 B로 가는데 몇단계를 거치는지 구하라는 얘기이다.

 

유저가 3명일때

1 : 1->2 , 1->3

2 : 2->1 , 2->3

3 : 3->1 , 3->2

 

노드 별로 n-1만큼의 경우가 있고 이 경우의 합이 가장 작은 노드의 번호를 구하면 된다.

 

양방향 그래프를 구현한 후 DFS나 BFS로 간선을 몇번 탔는지 구한다.

 

public class Main {
    
    static int n;
    static int a[][];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        a = new int[n+1][n+1];
        
        while(m-->0) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            
            a[v][u] = 1;
            a[u][v] = 1;
        }
        
        int seq = 0;
        int min = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++) {
            int sum = 0;
            for(int j=1; j<=n; j++)
                sum += bfs(i, j);
            
            if(min > sum) {
                min = sum;
                seq = i;
            }
        }
        System.out.println(seq);
    }
    
    public static int bfs(int s, int e) {
        Queue<Integer> q = new LinkedList<Integer>();
        
        q.offer(s);
        int cnt = 0;
        boolean find = false;
        while(!q.isEmpty()) {
            int size = q.size();
            
            while(size-->0) {
                int p = q.poll();
                if(p == e) {
                    find = true;
                    break;
                }
                for(int i=1; i<=n; i++)
                    if(a[p][i] == 1)
                        q.offer(i);
            }
            if(find) break;
            cnt++;
        }
        return cnt;
    }
}