[백준] 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
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *