[백준] 알고리즘 분류(너비 우선 탐색,JAVA)1389번, 케빈 베이컨의 6단계 법칙

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 케빈 베이컨의 법칙은 모든 사람은 6번에 관계를 이어지면 연결될 수 있다.

2. 케빈 베이컨 수는 각 인원이 다른 인원들을 연결하는 단계의 합입니다.

3. 케빈 베이컨의 수가 가장 작은 사람을 결과로 출력합니다.

4. 작은 사람이 여러명일 경우, 번호가 작은 사람을 결과로 출력합니다.

5. 사람의 번호는 1~N까지 주어집니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS으로 각 인원들의 케빈 베이컨의 수를 탐색합니다.

 

3. 가장 작은 케빈 베이컨의 수를 가진 사람의 번호 결과로 출력합니다.

 

 

케빈 베이컨의 수 탐색.

 

사람들의 관계를 그래프의 형태로 만듭니다.

※저는 그래프의 형태를 만들 때 ArrayList<ArrayList<Integer>> 형식으로 만들었습니다.

 

이후 각 인원들을 기준으로 BFS탐색을 진행하여 케빈 베이컨의 수를 구해서 최소값을 찾습니다.

 

진행되는 과정은 예제입력 1에서 보여드리겠습니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

N = 5

M = 5

 

2. BFS으로 각 인원들의 케빈 베이컨의 수를 탐색합니다.

 

BFS 탐색!

 

1번 사람

 

 

1 → 3, 1 → 4 : 1단계

1 → 2, 1 → 5 : 2단계

1 + 1 + 2 + 2 = 6

 

2번 사람

2 → 3 : 1단계

2 → 1, 2 → 4 : 2단계

 

2 → 5 : 3단계

1 + 2 + 2 + 3 = 7

 

3번 사람

3 → 1, 3 → 2, 3 → 4: 1단계

3 → 5 : 2단계

1 + 1 + 1 + 2 = 5

 

....

 

1번 사람 : 6

2번 사람 : 7

3번 사람 : 5

4번 사람 : 5

5번 사람 : 7

 

3. 가장 작은 케빈 베이컨의 수를 가진 사람의 번호 결과로 출력합니다.

 

가장 작은 케빈 베이컨의 수 : 5

 

3번 사람, 4번 사람

 

※문제 조건에 작은 사람이 다수일 때 적은 번호 사람을 결과로 출력합니다.

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N, M과 친구 관계를 띄어쓰기 기준 나누었습니다.
• bfs함수를 이용하여 각 인원을 기준으로 케빈 베이컨의 수를 탐색합니다.
• 탐색 종료 후 가장 작은 케빈 베이컨 수를 가진 사람의 번호를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS탐색을 이용하여 케빈 베이컨 수를 구한 뒤, 가장 작은지 비교합니다.

 

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //친구 관계 정보 그래프 형태로 저장할 리스트
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int N,min = Integer.MAX_VALUE, answer = -1;
    //BFS에 사용할 정보 클래스
    static class info{
        int index, count;
        public info(int index, int count){
            this.index = index;
            this.count = count;
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        //그래프 초기화
        for(int i=0;i<=N;i++)
            graph.add(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());
            graph.get(A).add(B);
            graph.get(B).add(A);
        }
        //각 인원 기준 BFS을 이용하여 케빈 베이컨 탐색 진행
        for(int i=1;i<=N;i++)
            bfs(i);
        //가장 작은 케빈 베이컨의 수를 가진 번호 BufferedWriter 저장
        bw.write(answer + "");	
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 케빈 베이컨 수 탐색하는 함수
    static void bfs(int start){
        Queue<info> queue = new LinkedList<>();	//BFS에 사용할 Queue
        boolean[] visited = new boolean[N+1];	//사람 방문 확인 배열
        queue.add(new info(start, 0));	//시작 번호 저장
        visited[start] = true;	//시작 번호 방문 확인
        int result = 0;
        //BFS 탐색 진행
        while(!queue.isEmpty()){
            info cur = queue.poll();
            //인접한 관계 탐색
            for(int next : graph.get(cur.index)){
                if(!visited[next]){		//방문하지 않았던 관계일 때
                    result += cur.count + 1;	//현재 단계 더하기
                    visited[next] = true;
                    queue.add(new info(next, cur.count+1));
                }
            }
        }
        //케빈 베이컨 수 비교
        if(result < min){
            min = result;
            answer = start;
        }

    }
}