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

hyeon·2022년 5월 16일
0

알고리즘 연습

목록 보기
12/23

문제 : 케빈 베이컨의 6단계 법칙

문제링크
실버 1
그래프 탐색

N의 케빈 베이컨 수는 N을 제외한 다른 유저와 만나기 위해 거쳐야할 각각의 단계수의 합을 말한다.
BOJ의 유저중 케빈 베이컨 수가 가장 작은 사람을 구하시오.

입력

유저의 수 N
친구 관계의 수 M
친구 관계 A,B (M줄)

출력

케빈 베이컨 수가 가장 작은 사람을 출력한다.
겹치는경우 가장 작은 사람을 출력

풀이

  1. 1~n까지 돌면서 각각의 단계수를 합한다.
    bfs를 사용해서 visited에 최단거리를 저장한다.
  2. visited를 모두 더한 후 MIN과 비교하여 더 작으면 MIN 갱신 후 index값 저장

코드

import java.util.*;

public class 백준1389 {
	static int n,m,cnt=0,answer=0;
	static int[][] arr;
	static int MIN=Integer.MAX_VALUE;
	static int[] visited;
	static Scanner scan =new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// 입력
		n=scan.nextInt();
		m=scan.nextInt();
		arr=new int[n+1][n+1];
		
		for(int i=0;i<m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			arr[a][b]=1;
			arr[b][a]=1;
		}
		for(int i=1;i<=n;i++) {	//각자의 베이컨 수 구하기
			int ans=0;
			visited=new int[n+1];
			bfs(i);
			for(int j=1;j<=n;j++) {
				ans+=visited[j];
			}
			if(MIN>ans-1) {
				answer=i;
				MIN=ans-1;
			}
		}
		System.out.print(answer);
	}
	static void bfs(int i) {
		Queue<Integer>q =new LinkedList<>();
		q.offer(i);
		visited[i]=1;
		while(!q.isEmpty()) {
			int nxt=q.poll();
			for(int a=1;a<=n;a++) {
				if(arr[nxt][a]==1&&visited[a]==0) {
					visited[a]=visited[nxt]+1;
					q.offer(a);
				}
			}
			
		}
	
	}
}
profile
남기고 싶은 개발자입니다 :>

0개의 댓글