Swift Coding Test Course, Kevin Bacon’s 6 Degrees of Separation

Problem Description

“The Six Degrees of Kevin Bacon” is a theory that all people can be connected to the actor Kevin Bacon through a maximum of six degrees of separation.
In this problem, based on a series of movie lists and information about the actors who starred in those movies, you need to calculate the degree of connection between each actor and Kevin Bacon.
You are required to calculate the shortest distance to Kevin Bacon for each actor from the given movie and actor information,
and find the actor with the shortest distance.

Problem Definition

The input provided is as follows.
– The first line contains the number of actors N (1 ≤ N ≤ 100) and the number of movies M (1 ≤ M ≤ 1000).
– Following this, M lines provide a list of actors appearing in each movie, separated by spaces.
Each line lists the names of the actors appearing in a movie.

The output should be the number of the actor closest to Kevin Bacon and that distance.

Approach to the Problem

To solve the problem, we will use a graph traversal algorithm.
Each actor will be a node, and if two actors appeared in the same movie, we connect them with an edge.
Then, we will use BFS (Breadth-First Search) to calculate the shortest path to Kevin Bacon.
The algorithm proceeds in the following order.

1. Create the graph. Define the relationships based on the movies the actors appeared in, treating each actor as a vertex.
2. Use BFS to calculate the distance to Kevin Bacon.
3. Compare the distances for all actors to find the shortest distance and the corresponding actor.

Example Input

    5 3
    A B C
    B D
    C D E
    

Example Output

    1 2
    

Code Implementation

Here is the algorithm implemented in Swift.
It creates a graph and measures the distance from each actor to Kevin Bacon using BFS.

        import Foundation

        func findKevinBaconNumber(N: Int, M: Int, movies: [[String]]) -> (Int, Int) {
            var graph = [String: [String]]()
            var distance = [String: Int]()
            
            // Create the graph
            for movie in movies {
                for i in 0..()
                var dist = 0
                
                while !queue.isEmpty {
                    let size = queue.count
                    for _ in 0..
Conclusion

        Today we covered an algorithm problem themed around "The Six Degrees of Kevin Bacon".

        Through this problem, we learned how to utilize graph theory and BFS.

        I hope this has been helpful in preparing for coding tests.

        We plan to continue with more problems and solutions, so please stay tuned.
    



	
관련