백준 JAVA 1389 케빈 베이컨의 6단계 법칙 리뷰

문제풀이

모든 친구를 방문해야하고 몇번째인지 구하는 게 전형적인 dfs/bfs 문제
근데 가장 작은 사람을 구하라고 했음 그래서 bfs로 접근하는게 맞다고는 생각하는데
10971은 최소 수 구하라면서 dfs만 사용 가능하거든 그래서 기준을 정확하게 모르겠다.

dfs/bfs 개념 다시 봐야겠다

1로 시작할때 베이컨 수
2로 시작할때 베이컨 수
..
이런식으로 해서 최소 베이컨 수인 사람 구해야하기 때문에 시작을 1일때 최소수 2일때 최소수 3일때 ... 경우를 모두 구해야하니까 for문 돌리면서 계속 bfs를 실행해야한다.

근데 1에서 3까지 2단계 3까지 1, 4까지 1 이런식으로 끊어서 그걸 모두 더한게 베이컨 수인데

1에서 5번간의 모든 친구 경로를 찾는다고 하자. 그냥 조건 없이 bfs 구하면 (1,3,4,5 ) 로 4가 나온다. 정답은 3인데. 

 

 depth[next]=depth[cur]+1;

 

depth를 구해서 저장하고 bfs가 끝날 때 for문 돌려서 다 저장하면 올바르게 베이컨 수의 합을 구할 수 있다.

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] gragh;
    static boolean[] visited;
    static int[] depth;
    static int sum;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();

        gragh =new ArrayList[N+1];

        for(int i=0; i<=N; i++){
            gragh[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            int A = scan.nextInt();
            int B = scan.nextInt();
            gragh[A].add(B);
            gragh[B].add(A);
        }
        int min =Integer.MAX_VALUE;
        int ans = -1;
        for(int i=1; i<=N; i++){
            depth = new int[N+1];
            visited = new boolean[N+1];
            bfs(i);

            if(min>sum) {
                min = sum; //케빈 베이컨 수 비교
                ans = i;
            }
            sum=0;
        }
        System.out.println(ans);
    }
    public static void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(int next:gragh[cur]){//인접 노드들 방문
                if(!visited[next]){
                    visited[next]=true;
                    depth[next]=depth[cur]+1;
                    queue.add(next);
                }
            }
        }
        for(int i=1; i<depth.length; i++){ //depth.length = N+1
            sum += depth[i];
        }
    }
}