[BOJ/JAVA] 백준 1389번 케빈 베이컨의 6단계 법칙 ( DFS, BFS )

 

✔ 문제

난이도 : 실버 🥈

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

 

✔ 문제 풀이

임의의 두 사람이 최소 몇 단계만에 이어질 수 있는지 계산하는 문제입니다.

즉, 정점에서 다른 정점까지의 최단거리들을 계산하여 최단거리들의 합이 가장 낮은 사람을 출력 해야합니다.

BFS와 DFS 모두 이용 가능하지만 DFS로 풀 경우 시간 초과가 났습니다.😭

하지만 풀이는 가능함으로 BFS와 DFS모두 풀어보겠습니다.

 

📌 설명은 코드 주석에 있습니다!

 

🔎 BFS 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new int[n+1]; // 방문 여부와 이전 단계를 계산하기위해 int배열로 생성해줍니다.

        /*
        * 인접한 리스트로 그래프를 표현하기 위해 리스트를 초기화 후
        * 리스트에 각 정점과 연결된 정점을 추가 해줍니다.
        * */
        friendship = new ArrayList[n + 1];
        for( int i = 1; i<=n; i++){
            friendship[i]=(new ArrayList<Integer>());
        }
        for( int i = 1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            friendship[x].add(y);
            friendship[y].add(x);
        }

        /*
        * 임의의 정점이 각 정점들과 연결된 단계들의 합 즉, cnt 중 가장 낮은 합을 갖는 정점을 구하기 위해
        * min, minIdx 선언하여 비교 후 가장 낮은 정점(사람)을 출력합니다.
        * */
        int min = Integer.MAX_VALUE;
        int minIdx = 0;
        for( int i = 1; i<=n; i++){
            int cnt = bfs(i);
            if( min > cnt ){
                min = cnt;
                minIdx = i;
            }
        }

        System.out.println(minIdx);

	}
    
    /*
    * visited배열은 방문여부와 연결 단계를 계산하기위해 -1로 세팅합니다.
    * 전체 정점에대한 관계를 구해야하기 때문에 시작 정점을 매개변수로 받아 queue에 넣고,
    * 정점과 연결된 정점을 찾기 위해 for문을 통하여 방문하지 않은 연결된 정점들도 차례로 queue에 넣습니다.
    * 이때 정점과 정점 사이의 연결된 단계를 측정해야 하기 때문에 이전 단계 + 1을 하여 현재 정점에 세팅해줍니다.
    * 세팅된 단계수는 cnt변수에 누적산하여 리턴해줍니다.
    * */
    static int bfs(int start){
        Arrays.fill(visited,-1);
        visited[start] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        int cnt = 0;
        while (!queue.isEmpty()){
            int prevIndex = queue.poll();
            for( int index : friendship[prevIndex]){
                if( visited[index] == -1 ){
                    queue.offer(index);
                    visited[index] = visited[prevIndex] + 1;
                    cnt += visited[index];

                    //System.out.print(visited[index]); // 예제1 : 1122  1223  1112  1112  1223
                }
            }
        }

        return cnt;

    }
}

 

🔎 DFS 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main{

	static boolean[] visited;
    static ArrayList<Integer>[] friendship;
    static int answer;
    static int[] result;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        StringTokenizer st;
        
        nt n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new boolean[n + 1];
        friendship = new ArrayList[n + 1];
        for( int i = 1; i<=n; i++ ){
            friendship[i] = new ArrayList<>();
        }

        for( int i = 0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            friendship[y].add(x);
            friendship[x].add(y);
        }

        /*
        * 하나의 정점과 나머지 모든 정점과의 관계를 계산하기 위해 이중 for문을 사용하여
        * 자신과 자신을 제외한(i != j) 정점들에 대해 dfs알고리즘을 수행합니다.
        * */
        result = new int [n+1];
        for( int i = 1; i<=n; i++){
            for( int j = 1; j<=n; j++){
                answer = Integer.MAX_VALUE;
                visited = new boolean[n + 1];
                if( i != j ){
                    dfs(i, j, 0);
                    result[i] += answer;
                }
            }
        }

        int min = Integer.MAX_VALUE;
        int idx = 0;
        for( int i = 1; i<=n; i++ ){
            if( min > result[i] ){
                min = result[i];
                idx = i;
            }
        }

        System.out.println(idx);

	}
    
    /*
    *  start : 시작 정점
    *  end : 끝 정점 ( 시작 정점과 끝 정점까지 탐색합니다 )
    *  cnt : 연결 단계를 계산하기 위한 매개변수 ( start - end 까지 연결된 단계의 수 )
    *
    *  재귀호출한 dfs가 탐색 목적지인 끝정점까지 도착했다면 if(start == end)
    *  최소값을 설정 후 dfs를 종료합니다.
    *  dfs는 최단거리가 아닌 연결된 모든 경로를 계산하기 때문에 연결된 경로중 가장 작은 값을 구해야합니다.
    * */
    static void dfs(int start, int end, int cnt){
        if( start == end ){
            answer = Math.min(answer, cnt);
            return;
        }
        visited[start] = true;
        for( int i : friendship[start]){
            if( !visited[i] ){
                dfs(i,end, cnt+1);
            }
        }

    }
}