[백준] no1389: 케빈 베이컨의 6단계 법칙

문제

* 케빈 베이컨의 6단계 법칙
* : 모든 사람과 두루 가깝게 지내는 사람 구하기
* : 즉, 다른 모든 인원과 몇 다리 걸쳐야 하는지 구한 거리수의 총합이 가장 적은사람이 케빈 베이컨

Input :

1. 첫 째줄에 인원수와 연결 수가 주어짐

2. 둘 째줄부터 연결된 시작점과 끝점이 주어짐

 

Output :

전체 인원 중, 다른 인원과의 거리의 합이 제일 작은 수인 인원의 위치를 반환

 

문제 링크 : https://www.acmicpc.net/problem/1389

---

원리

필자는 BFS를 이용해서 구하는 방법을 사용했다.

---

풀이방법

[Main 메서드]

1. 모든 인원을 각각 1부터 N번 인덱스에 배치

2. 각 인덱스별로 시작지점을 한 명씩 뽑는 반복문을 돌림

3. 각 인덱스별로 도착지점을 한 명씩 뽑는 이중반복문을 돌림

4. 뽑은 시작지점과 도착지점을 넣어서, 도달하는데 걸리는 거리 중 가장 짧은 이동 거리를 반환하는 BFS 메서드를 돌림

 

[BFS메서드]

1. 대기열을 만들어서 우선 처음 입력으로 들어온 시작지점, 도착지점, 이동거리수(count)를 갖는 객체를 넣어줌

2. 이제 대기열이 빌 때까지 반복해줄거임

3. 대기열에서 객체(now)를 하나씩 뽑아서 현재 객체의 출발지점과 목표지점이 같으면, 여태 이동한 거리수를 기록

4. 그 외에는 다시 다음에 이동할 위치를 대기열에 넣어주기위한 반복문을 돌림

5. 단, 이동할 수 있는 경로가 연결되어 있고(int[ ][ ] map으로 확인), 방문한 적이 없는 경우(!visited[ ])에만 넣어줌

6. 대기열에 넣을 땐, 지금 도착한 곳에서 다시 출발해야 하며, 목표지점은 동일함. 이동 했으므로 count+1해줌

7. 모든 탐색이 끝나면, 기록된 거리 중 가장 짧은 거리를 반환함

 

[Node 이너클래스]

1. BFS용 객체를 만들어주기 위함

2. 출발지점, 도착지점, 여태 이동한 거리 수를 인자로 갖게됨 

---

나의 코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class no1389 {
    private static int node;
    private static int edge;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력받는 구간 : 노드 수와 간선 수가 주어진다
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        map = new int[node+1][node+1]; // 1번부터 node번까지의 위치를 탐색하기 위함 (0번 인덱스때문)

        for (int i = 0; i < edge; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
            int departure = Integer.parseInt(st2.nextToken());
            int arrival = Integer.parseInt(st2.nextToken());
            map[departure][arrival] = map[arrival][departure] = 1;
        }

        // BFS 탐색을 위해 시작, 목표 지점을 정해서 반복해주는 구간
        int[] results = new int[node+1];
        results[0] = Integer.MAX_VALUE;
        for(int start = 1; start <= node; start++) {
            int sum = 0; // 시작지점에서 각 목표 지점으로 도착했을 때, 최단 거리들을 합산해주기 위한 역할
            for(int goal = 1; goal <= node; goal++) {
                if(start!=goal) sum += BFS(start, goal); // 각 지점까지 도달한 최단 거리를 반환해준 것을 합산
            }
            results[start] = sum; // 모든 인원에 대한 최단 거리를 합한 값을 출발지점의 인덱스에 기록
        }

        // 최솟값 찾기
        int min = Integer.MAX_VALUE; // 최소값으로 비교하기 위해 기준값은 최대값으로 설정
        int answer = 0; // 최소값을 가진 인덱스를 기록하기 위함
        for(int i=results.length-1; i>0 ; i--) {  // 같은 최단거리를 가질 경우, 더 작은 인덱스에 있는 인원을 고르기 위해 역순으로 계산
            if(results[i]<=min) {
                min = results[i]; // 최소값 기록
                answer = i;  // 최소값을 가진 인덱스 기록
            }
        }

        System.out.println(answer); // 반환값은 최단거리의 합이 아닌, 해당 인원의 위치이므로 answer를 반환. (만약 총 합 거리를 원할 시 min을 반환)
    }

    private static int BFS(int start, int goal) {
        Deque<Node> dq = new ArrayDeque<>(); // 대기열
        dq.add(new Node(start, goal, 0)); // 처음 시작지점
        boolean[] visited = new boolean[node+1]; // 방문 체크
        List<Integer> tempList = new ArrayList<>(); // 도달 거리들을 기록하는 용도

        while(!dq.isEmpty()) {
            Node now = dq.poll();
            if(now.start==now.end) tempList.add(now.count);
            for(int i=1; i <= node ; i++) {
                if(map[now.start][i]==1 && !visited[i]) {
                    visited[i] = true;
                    dq.add(new Node(i,goal, now.count+1)); // 방금 도착한 지점이 곧 다음 출발지점이 됨. 이동 했으므로 직전 이동거리+1
                }
            }
        }
        return Collections.min(tempList); // 기록 중 최단거리를 구해서 반환
    }

    private static class Node {
        private int start;
        private int end;
        private int count;
        public Node(int start, int end, int count) {
            this.start = start;
            this.end = end;
            this.count = count;
        }
    }
}