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

백준 1389번 문제 - 케빈 베이컨의 6단계 법칙

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

---

문제 분석 

 

 

• 사람 수가 정해지고 친구 사이 거리가 1인 조합이 주어진다.
• 이 때, 나를 제외한 나머지 사람들과의 친구 사이 거리의 합이 가장 적은 사람의 INDEX를 출력해라
  • 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력해라
• 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.
  1의 친구 사이 거리 합 : 2+1+1+2 = 6
  2의 친구 사이 거리 합 : 2+1+2+3 = 8
  3의 친구 사이 거리 합 : 1+2+1+2 = 5
  4의 친구 사이 거리 합 : 1+2+1+2 = 5
  5의 친구 사이 거리 합 : 2+3+2+1 = 8
  여기서 답은 친구사이의 거리의 합이 5인 3, 4이다. 즉 답은 3이다.

---

 

해결 포인트

 

 

• BFS 사용
• BFS 사용해서 각 index에 친구 사이 합을 구한다.
  • sum을 0으로 초기화, count는 1로 초기화
  • 큐에 해당 index 추가, 방문 체크
  • 현재 큐에 담아있는 을 다 빼서 해당 INDEX에 친구 관계 중 방문하지 않은 경우 큐에 추가
    큐에 추가하면서 방문 체크 및 sum 값에 count 추가 
  • 다 확인 했으면 count 증가
  • 큐가 빌 때까지 반복

 

Boolean과 boolean

 

처음에 visit 확인할 때 nullPointer Error 발생

• visit를 Boolean 배열로 구현하였는데 해당 문제 발생.
• visit를 boolean 배열로 변경하니 문제 해결. 

 

왜일까?!

 

Boolean은 객체 자료형이고 초기화되지 않은 상태에서는 기본적으로 null을 가진다.

따라서 Boolean 배열로 선언한 경우, 배열의 각 요소는 초기화되지 않아 null 상태가 된다.

이로 인해 if (!visit[value])에서 null을 체크하면서 NullPointerException이 발생할 수 있다.

 

boolean은 기본 자료형으로서 자동으로 초기화된다.

초기화되지 않은 boolean 배열의 각 요소는 false로 초기화됩니다.

따라서 boolean 배열로 선언한 경우 초기화 문제가 발생하지 않습니다.

---

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static ArrayList<Integer>[] friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        friends = new ArrayList[N + 1];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            friends[a].add(b);
            friends[b].add(a);
        }

        int min = 99999999;
        int minIndex = 0;
        for (int i = 1; i <= N; i++) {
            int value = BFS(i, N);
            if (value < min) {
                min = value;
                minIndex = i;
            }
        }

        bw.write(minIndex + "\n");
        bw.flush();
        bw.close();
    }

    public static int BFS(int index, int N) {
        boolean[] visit = new boolean[N + 1];
        Queue<Integer> queue = new LinkedList<>();

        int sum = 0;

        visit[index] = true;
        queue.add(index);

        int count = 1;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int q = 0; q < queueSize; q++) {
                Integer newIndex = queue.poll();
                for (int value : friends[newIndex]) {
                    if (!visit[value]) {
                        visit[value] = true;
                        queue.add(value);
                        sum += count;
                    }
                }
            }
            count++;
        }

        return sum;
    }
}