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

solved.ac = 실버 1

https://www.acmicpc.net/problem/1389

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

 

1. 접근

 

이러면 혹시 나도 대통령이랑 친ㄱ....

먼저 최대값과 시간 복잡도를 구해보자면 모든 관계를 다 둘러보아도 5,000번이면 되니 최대값은 넉넉하고 시간 복잡도로는 유저(간선)마다 각각의 케빈 베이컨 수를 구해야 하니 (유저 수 + 관계) * 유저수 = 100,000로 시간 또한 넉넉하다.

 

문제의 설명을 그래프와 표로 정리하자면 다음과 같다.

1번 유저가 2번 유저까지 두 다리, 3번 유저까지 한 다리, 4번 유저까지 한 다리, 5번 유저까지 두 다리로 총 합은 6이 된다.

표와 같이 각 유저의 케빈 베이컨의 수를 구해주고 최소값을 가지고 있는 최소 인덱스를 출력해주면 된다!

 

2. 접근

 

전역 변수 및 input

static int N, M;
static ArrayList<Integer>[] graph;
static int[] dist;
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 친구의 수(V)
    M = Integer.parseInt(st.nextToken()); // 관계의 수(E)
    dist = new int[N + 1]; // 카운트 체크
    graph = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int i = 1; i <= M; i++) {
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
        graph[x].add(y); // x번 유저와 y번 유저는 연결되어 있다!
        graph[y].add(x); // 무방향 그래프로 반대 입장도 연결하자!
    }

    solution();
}

 

BFS 호출 및 최소값 비교

// N만큼 각각 BFS를 돌려 최댓값을 갱신한다.
static void solution() {
    int minCnt = Integer.MAX_VALUE, minIdx = 0; // 최소 카운트와 해당 정점 번호
    for (int i = 1; i <= N; i++) {
        int cnt = BFS(i);
        if (minCnt > cnt) { // 최소 카운트 및 정점 번호 갱신
            minCnt = cnt;
            minIdx = i;
        }
    }
    System.out.println(minIdx);
}

 

BFS

static int BFS(int start) {
    Arrays.fill(dist, -1); // 방문여부 및 카운트 초기화
    int cnt = 0;
    Queue<Integer> Q = new LinkedList<>();
    Q.add(start);
    dist[start] = 0;

    while(!Q.isEmpty()) {
        int x = Q.poll();
        for (int y : graph[x]) {
            if (dist[y] != -1) continue;
            dist[y] = dist[x] + 1;
            cnt+= dist[y]; // 이동 횟수를 누적해주자!
            Q.add(y);
        }
    }
    return cnt;
}

 

3. 전체코드