[ Baekjoon - 10/24 ] - 1389번: 케빈 베이컨의 6단계 법칙

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

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

 

• 소요 시간 : 50분

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 유저 N명(2≤N≤100), 친구 관계의 수 M개(1≤M≤5,000)
     • 주어진 N명의 사람이 최소 한명씩이랑 친구관계인데, 가장 인맥을 덜 거쳐도 알 수 있는 최소의 관계수를 출력하는 문제
     • 즉, 모두가 나와 누구를 통하지않고 바로 친구관계라면 가장 최소의 관계수를 가진사람은 나일 것이다.
       다만, 같은 관계수라면 숫자가 작은사람을 출력한다.
   • 이해
     • 문제를 읽자마자 그래프를 그려야할 것 같았고, 인접한 사람들에게로 가는 식이므로 BFS와 인접리스트를 활용해야겠다고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 이렇게 그려보며 BFS를 돌리면 되겠다고 생각했다. (후에 틀린 원인은 여기에 있었는데, 무방향임에도 인접리스트를 방향그래프처럼 그려놓았다... )
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 인접리스트와 BFS)
     • 친구 "관계"가 중요하고, 각 사람들(노드)로 부터 얼마나 덜 거쳐가야 다 관계가 이어지는지 판단해야하므로, 깊게만 가는 DFS보단 BFS가 적절하고, BFS와 잘 어울리는 인접리스트를 선택했다.
     • 모든 노드에 대해 BFS를 한번씩 전부 돌리는데, 
       본인으로부터 갈 수 있는 곳을 쭉 가고, 후에 갈수있는 사람으로 부터 다시 갈수있는 곳을 쭉 가고... 반복하며
       모두를 만날때 까지 돌리면된다.
     • 정수형 변수하나로 하기엔 누구를 만났었고, 누구를 못만났는지 모르므로, 리스트를 하나 선언하여 각 인덱스에 만남여부를 기록했다.
4. 위 계획을 검증
   • BFS의 기본틀안에서 실행가능하므로, 크게 검증은 필요없다. BFS시간복잡도도 큰편이 아니므로 무난히 실행됨!
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.util.*;
         import java.io.*;
         
         public class Main{
             static int N,M,minValue=Integer.MAX_VALUE,minIdx=-1;
             static List<Integer>[] adjList;
         
             public static void main(String[] args) throws IOException {
                 //System.setIn(new FileInputStream("src/input.txt"));
         
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                 StringTokenizer st = new StringTokenizer(br.readLine());
                 N =Integer.parseInt(st.nextToken());
                 M =Integer.parseInt(st.nextToken());
         
                 adjList = new ArrayList[N+1];
                 for (int n = 1; n < N+1; n++) {
                     adjList[n] = new ArrayList<>();
                 }
         
                 for (int m = 0; m < M; m++) {
                     st = new StringTokenizer(br.readLine());
                     int idx = Integer.parseInt(st.nextToken());
                     int val = Integer.parseInt(st.nextToken());
                     // 양방향
                     adjList[idx].add(val);
                     adjList[val].add(idx);
                 }
         
                 for (int person = 1; person < N+1; person++) {
                     int cur = BFS(person);
                     if(minIdx==-1 || minValue > cur){
                         minIdx = person;
                         minValue = cur;
                     }
                 }
                 System.out.println(minIdx);
         
             }
         
             private static int BFS(int person) {
                 // 해당 idx를 방문하면 1로 바꿔서 어느 숫자를 방문했는지 알기위한 배열
                 int[] jud = new int[N+1];
                 Queue<Point> queue = new LinkedList<>();
                 queue.add(new Point(person,1));
         
                 while (!queue.isEmpty()){
                     Point node = queue.poll();
                     for (int p = 0; p < adjList[node.point].size(); p++) {
                         int idx = adjList[node.point].get(p);
                         if(jud[idx]==0) {
                             queue.add(new Point(idx, node.move+1));
                             jud[idx] = node.move;
                         }
                     }
         
                     int sum=0;
                     for (int n = 1; n < N+1; n++) {
                         if(jud[n]==0)
                             break;
                         else if (n==N && jud[n]!=0) {
                             return sum+jud[n]-jud[person];
                         }
                         sum+=jud[n];
                     }
                 }
                 return -1;
             }
         }
         
         class Point{
             int point;
             int move;
         
             public Point(int point, int move) {
                 this.point = point;
                 this.move = move;
             }
         
             @Override
             public String toString() {
                 return "Point{" +
                         "point=" + point +
                         ", move=" + move +
                         '}';
             }
         }

 

• 결과

틀린 이유는 위에서도 언급했지만, 무방향 그래프라고 생각은 해놓고, 인접리스트는 방향그래프로 구현해서 오류가 발생했다.