케빈 베이컨의 6단계 법칙(1389)

케빈 베이컨의 6단계 법칙(1389)

import java.io.*;
import java.util.*;

public class Main{
    
  static boolean[][] friend; // 정점과 간선
  static boolean[] visited; // 방문 체크
  static int[] predecessor; // 이전 정점
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    
    friend = new boolean[n+1][n+1];
    visited = new boolean[n+1];
    predecessor = new int[n+1];
    
    int[] cnt = new int[n+1]; // 경로의 합
    
    for(int i = 0; i < m; i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
      friend[a][b] = true;
      friend[b][a] = true;
    }
    
    for(int i = 1; i <= n; i++){
      BFS(i, n);
      
      // 현재 번호의 케빈 베이컨
      for(int j = 1; j <= n; j++){
        if(i == j) continue;
        
        int num = j; // 타겟
        
        //백트레킹 하며 카운트
        while(true){
          if(num == i) break;
          num = predecessor[num];
          cnt[i]++;
        }
      }
      
      // 배열 초기화
      Arrays.fill(visited, false);
      Arrays.fill(predecessor, 0);
    }
    
    int min = Integer.MAX_VALUE;
    int res = 0;
    
    for(int i = 1; i <= n; i++){
      if(cnt[i] < min){
        min = cnt[i];
        res = i;
      }
    }
    
    sb.append(res);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  // BFS
  public static void BFS(int start, int n){
    Deque<Integer> deque = new ArrayDeque<>();
    
    deque.offerFirst(start);
    predecessor[start] = -1;
    
    while(!deque.isEmpty()){
      int num = deque.pollLast();
      if(visited[num]) continue;
      
      visited[num] = true;
      for(int i = 1; i <= n; i++){
        if(friend[num][i]){
          if(predecessor[i] == 0) predecessor[i] = num;
          deque.offerFirst(i);
        }
      }
    }
  }
}

풀이과정

1. BFS가 최단경로를 찾아내는데 사용된다는 것을 알고 있었다.
2. 하지만 BFS의 원리는 알고 왜 최단경로를 찾는데 좋다는지 알겠는데 코드로 구현하려니 떠오르지 않았다.
3. BFS에 대해서 공부를 해보니 predecessor의 개념을 알게 되었고, 이게 백트래킹이라는 것을 알게되었다.

- 성공
- 메모리 : 15448 KB
- 시간 : 172 ms

보안점

1. 나는 일단 predecessor를 이용하여 전 정점의 수를 기록하고, 나중에 백트래킹을 하며 카운트하였다.
2. 근데 문제에서 원하는 답은 모든 타겟의 최소 거리의 합이기 때문에 이전 정점이 누군지 보다는 시작점에서 각 지점들 까지의 거리를 기록하고
3. 기록된 거리들의 합을 구하면 되는 것이었기 때문에 정점을 기록하기 보다는 거리를 기록하였다면, 총 거리를 찾기 위한 for문을 안돌렸어도 될 듯 하였다.