[백준/JAVA] 1389번: 케빈 베이컨의 6단계 법칙

🔺 문제

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

이 아저씨 얼굴만 알았는데 이름이 케빈 베이컨이었구나

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int INF = 10000001;
    static int[][] distance; // 양방향 인접 행렬
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int N = Integer.parseInt(st.nextToken());   // 유저 수
        int M = Integer.parseInt(st.nextToken());   // 친구 관계 수
        
        // 인접 행렬 채우기
        distance = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(i == j) distance[i][j] = 0;
                else       distance[i][j] = INF;
            }
        }
        
        for(int i = 1 ; i <= M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            distance[a][b] = distance[b][a] = 1; // 양방향
        }
        
        // 플로이드-워셜
        for(int k = 1 ; k <= N ; k++) {
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
        
        // 케빈 베이컨 수 계산
        int min = Integer.MAX_VALUE;
        int answer = -1;
 
        for(int i = 1 ; i <= N ; i++) {
            int tmp = 0;
            
            for(int j = 1 ; j <= N ; j++) {
                tmp += distance[i][j];
            }
            if(min > tmp) {
                min = tmp;
                answer = i;
            }
        }
 
        System.out.println(answer);
    }
}

✅ 해결 아이디어
✔ 플로이드-워셜

 

---

🔺 다른 풀이들

- BFS를 쓰셨다.

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

[Java] 백준 1389번 [케빈 베이컨의 6단계 법칙] 자바

 

---

💬 느낀 점

어려운 문제가 아닌데 마지막에 케빈 베이컨 수 계산하는 부분에서 이상하게 시간 많이 잡아먹었다...ㅠ

분발하자ㅏㅏㅏㅏ

 

 

 

1회독	2회독	3회독	4회독	5회독
V	230627	240514

 

 

(+ 6/27 2회독)

플로이드-워셜은 알고보니 dp였던 건에 관하여...

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] dp;  // 인접 행렬
    static int INF = 10000001;    // 🔔 Integer.MAX_VALUE로 하면 X
    
    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());   // 친구관계 수
        
        // dp 배열 초기화
        dp = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                dp[i][j] = (i == j) ? 0 : INF;
            }
        }
        
        // 입력 받아 dp 배열 채우기
        while(M --> 0) {
             st = new StringTokenizer(br.readLine(), " ");
             int a = Integer.parseInt(st.nextToken());
             int b = Integer.parseInt(st.nextToken());
             
             dp[a][b] = dp[b][a] = 1;
        }
        
        // dp 배열 업데이트 (최솟값으로)
        for(int k = 1 ;  k <= N ; k++) {
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(dp[i][j] > dp[i][k] + dp[k][j]) {
                        dp[i][j] = dp[i][k] + dp[k][j];
                    }
                }
            }
        }
        
        // 최소값 출력하기
        int min = Integer.MAX_VALUE;
        int answer = -1;
        
        for(int i = 1 ; i <= N ; i++) {
            int tmp = 0;
            for(int j = 1 ; j <= N ; j++) {
                tmp += dp[i][j];
            }
            
            if(min > tmp) {
                min = tmp;
                answer = i;
            }
        }
        System.out.println(answer);
    }
}
 

 

 

(+240514 3회독 : 14700KB, 152ms)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());   // 유저 수
        int M = Integer.parseInt(st.nextToken());   // 친구 관계 수
        
        int[][] dp = new int[N+1][N+1];
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // 양방향
            dp[a][b] = 1;
            dp[b][a] = 1;
        }
        
        // [플로이드-워셜] dp 배열 채우기
        for(int k = 1 ; k <= N ; k++) { // 경유지
            for(int i = 1 ; i <= N ; i++) { // 출발지
                for(int j = 1 ; j <= N ; j++) { // 도착지
                    if(i==j || j==k || k==i)    continue;
                    
                    if(dp[i][k] != 0 && dp[k][j] != 0) {    // 출발지와 도착지를 연결하는 경유지가 있으면
                        if(dp[i][j] == 0)   // 친구 관계가 없으면 값 그대로 넣기
                            dp[i][j] = dp[i][k] + dp[k][j];
                        else    // 이미 친구 관계가 있다면, 더 작은 케빈 베이컨 수 넣기
                            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                    }
                }
            }
        }
        
        int min = 5000; // 최소 케빈 베이컨 수
        int answer = 0; // 번호가 가장 작은 사람
        
        for(int i = 1 ; i <= N ; i++) {
            int tmp = 0;
            
            for(int j = 1 ; j <= N ; j++) {
                if(i != j)
                    tmp += dp[i][j];
            }
            
            if(tmp < min) {
                min = tmp;
                answer = i;
            }
        }
        System.out.println(answer);
    }
}