백준 알고리즘 - 케빈 베이컨의 6단계 법칙 (1389번)

케빈 베이컨의 6단계 법칙

☞ 문제링크

최단 경로 문제로 BFS탐색을 이용해서 풀어야 하는 문제였습니다. 

문제의 예시로 그래프를 만들면 아래와 같습니다.

문제 풀이 (java)

1. 그래프 탐색에서의 노드를 케빈 베이컨 게임의 참가한 유저로 치환하여 클래스를 만들어 줍니다.

class User {
    private int index;
    private List<User> friends;
    private boolean checked;
   . . . 
}

2. 일반 노드와 다른 점은 step이라는 필드가 선언되어 있습니다. 이건 케빈 베이컨 점수를 계산하기 위해서 선언된 필드 입니다. 자세한 사항은 아래에서 설명 하겠습니다.

class User {
    private int index;
    private List<User> friends;
    private boolean checked;
    private int step;
    private int kevinBacon;
   . . . 
}

3. 만약 User 1의 케빈 베이컨 점수를 알고 싶다면. User 1을 큐에 제일 먼저 넣습니다. 그리고 이때 제일 먼저 들어온 User1의 step 필드는 0으로 들어갑니다.

class Graph {
    . . .
    //파라미터로 들어온 user의 케빈베이컨을 계산하는 메소드
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);
        . . .
}

4. 이제부터 큐가 비어질 때 까지 (empty) 아래와 같은 과정을 합니다.

class Graph {
    . . .
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);

        while (!queue.isEmpty()) {
            . . .
        }
    }
}

5. 큐에서 User(노드)를 하나 꺼냅니다. 

class Graph {
    . . .
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);

        while (!queue.isEmpty()) {
            User peek = queue.peek();
            . . .
        }
    }
}

6. 그 꺼낸 노드의 인접 노드 중 (친구관계인 User중)에 큐에 들어오지 않았던 User를 큐에 추가합니다. 

class Graph {
    . . .
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);

        while (!queue.isEmpty()) {
            User peek = queue.peek();
           for (User friend : peek.getFriends()) {
                if (!friend.isChecked()) {
                    friend.setChecked(true);
                    friend.setStep(peek.getStep() + 1);
                    queue.add(friend);
                }
              . . .
}

7. 추가한 큐의 step은 (5번 과정에서) 꺼낸 큐의 +1로 들어갑니다.

class Graph {
    . . .
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);

        while (!queue.isEmpty()) {
            User peek = queue.peek();
           for (User friend : peek.getFriends()) {
                if (!friend.isChecked()) {
                    friend.setChecked(true);
                    friend.setStep(peek.getStep() + 1);
                    queue.add(friend);
                }
              . . .
}

8. (5번 과정에서) 꺼낸 큐의 step을 현재 user의 케빈베이컨 점수에 더 해줍니다.

class Graph {
    . . .
    private void calcKevinBacon(User user){ 
        Queue<User> queue = new LinkedList<>();
        queue.add(user);

        while (!queue.isEmpty()) {
            User peek = queue.peek();
           for (User friend : peek.getFriends()) {
                if (!friend.isChecked()) {
                    friend.setChecked(true);
                    friend.setStep(peek.getStep() + 1);
                    queue.add(friend);
                }
            }
            user.addKevinBacon(queue.poll().getStep());
              . . .
}

9. 이제 큐에서 다음 노드를 꺼냅니다. (4번 부터 반복)
10. 이런 식으로 각 User의 케빈 베이컨 점수를 모두 계산하고 가장 낮은 점수를 가지고 있는 User를 반환하면 됩니다.

배운점

• 최단 경로 문제는 BFS 풀어야 한다는 점을 기억해둬서 빨리 풀 수 있었다.
• step이라는 필드는 선언하고 들어갈때 계산 한다는 점을 코딩 전에 좀 더 침착하게 생각 했어야 했는데, 너무 급하게 그래프 부터 구현했던 것 같다.
• (적절한 필드값을 추가하는 것이 좋다는 것을 배웠다.)
• 입력 설명 중에 '친구 관계가 중복으로 들어 올 수 있다' 라는 점을 캐치해내서 처음부터 고려하여 코딩했다. (뿌듯)

---

☞ 문제 풀이 코드 Git hub 주소