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

문제 1389번 (bfs)

 :  모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.

    케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임

 

 :  BOJ의 유저가 5명이고, 1 - 3, 1 - 4, 2 - 3, 3 - 4, 4 - 5 친구인 경우

   1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다

   케빈 베이컨의 수는 2+1+1+2 = 6

 

 

 [입력]

 :  첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)

    둘째 줄부터 M개의 줄에는 친구 관계

 

 

[출력]

 :  첫째 줄에 케빈 베이컨의 수가 가장 작은 사람을 출력 (여러 명일 경우에는 번호가 가장 작은 사람)

 

 [과정]

 

1. int[] 말고 arraylist 사용

• 다차원 배열이 아닌 arraylist에 여러 값을 추가하는 방식으로 진행

 

2. 인덱스 출력 

• 관계 연결 카운트가 아니라 카운트가 적은 정수를 출력한다 (즉, 인덱스) 
• bfs(i)가 최소일 경우 i라는 index이자 정수를 뽑아 출력할 것
• sum이 아닌 who 출력

 

3. void가 아닌 int 사용

• void를 사용하려면 return이 아닌 System.out.println으로 바로 출력해야 한다
• return을 사용하기 위해서 int로 변경

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M,A,B;
    static ArrayList<Integer> arr[];
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new ArrayList[N + 1]; 
        for(int i=1;i<=N;i++){
            arr[i]=new ArrayList<>();
        }
        
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            arr[A].add(B);
            arr[B].add(A);
        }
        
        int result=Integer.MAX_VALUE;
        int who = 0;
        for(int i =1; i<=N; i++){
            if(bfs(i)<result){
                result = bfs(i);
                who = i;
            }
        }
        
        System.out.println(who);
    }
    static int bfs(int start){
        Queue<int[]> q = new LinkedList<>();
        visit = new boolean[N+1];
        visit[start] = true;
        q.add(new int[] {start,0});
        
        int sum =0;
        while(!q.isEmpty()){
            int[] p = q.poll();
            for(int i=0; i<arr[p[0]].size();i++){
                int next = arr[p[0]].get(i);
                if(!visit[next]){
                    visit[next] = true;
                    q.add(new int[]{next, p[1]+1});
                    sum += p[1]+1;
                }
            }
        }
        return sum;
        
    }
}

 

 [해설]
     

 :  static int N,M,A,B;  
    static ArrayList<Integer> arr[];
    static boolean visit[];

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  입력1 정수 개수
    M = Integer.parseInt(st.nextToken());  입력2 정수 관계수
        
 :  arr = new ArrayList[N + 1];  배열크기 지정
    for(int i=1;i<=N;i++){  입력이 1부터 받기 때문에 1부터 정수 개수 만큼 인덱스 생성
            arr[i]=new ArrayList<>();  
    }
        
 :  for(int i=0; i<M; i++){  i를 인덱스로 활용하지 않고 단순 M만큼 반복이기 때문에 0부터 시작
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());  연결된 관계 추가
            B = Integer.parseInt(st.nextToken());  거꾸로도 관계 추가
            arr[A].add(B);  예) 3 - 4 이면 arr[3] = 4, arr[4] = 3 이렇게 두 번 다 추가해준다
            arr[B].add(A);        
    }
        
 :  int result=Integer.MAX_VALUE;  우리는 최소값을 찾아야 하므로 MAX로 초기화
    int who = 0;  최소값을 가진 정수 즉 인덱스 출력하기 위해서 지정
    for(int i =1; i<=N; i++){  
            if(bfs(i)<result){  bfs 돌리고 result보다 작다고 하면 
                result = bfs(i);  result 갱신
                who = i;  해당 index를 바로 추출
            }
    }
        
 :  System.out.println(who);  who 출력
    

 :  static int bfs(int start){  연결 시작 정수
        Queue<int[]> q = new LinkedList<>();  큐생성
        visit = new boolean[N+1];  방문 초기화
        visit[start] = true;  방문처리
        q.add(new int[] {start,0});  큐에 시작 정수 / 관계수 카운트 추가
        
        int sum =0;
        while(!q.isEmpty()){
            int[] p = q.poll();  큐에서 뽑고
            for(int i=0; i<arr[p[0]].size();i++){  큐 0번째인 시작 정수를 인덱스로 넣어 그 크기만큼 돌리기
                int next = arr[p[0]].get(i);  다음 시작 정수를 지금 인덱스와 연결된 다른 정수들로 설정
                if(!visit[next]){  방문하지 않았다면
                    visit[next] = true;  방문처리 후
                    q.add(new int[]{next, p[1]+1});  큐에 다음정수 추가 / 관계수 카운트
                    sum += p[1]+1;  합 계산
                }
            }
        }
        return sum;
    }

   

 

      

이제 풀어보러 갈께요 :)

 

 

 

 

 

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

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *