Kotlin Coding Test Course, Kevin Bacon's Six Degrees of Separation

In this course, we will explore ‘Kevin Bacon’s Six Degrees of Separation’ and examine the process of solving related algorithm problems. Kevin Bacon’s Six Degrees of Separation is the theory that everyone is connected to Kevin Bacon within six degrees. Based on this, we will solve problems using graph theory.

Problem Description

The problem is to represent given people and their relationships in the form of a graph, and to identify how a specific individual relates to all other individuals. We define the problem as follows:

Problem: Kevin Bacon's Six Degrees of Separation

Given n people and m relationships.
People are represented by integers from 1 to n.
Each relationship is given by the IDs of two people, indicating that they are friends.
Please calculate each person's Kevin Bacon number. The Kevin Bacon number is the length of the shortest path from that person to another person.
Finally, print the ID of the person with the smallest Kevin Bacon number. If there are multiple individuals, select the one with the smallest ID.

Input Format

  
ID1 ID2
ID1 ID3
...

Output Format

The ID of the person with the smallest Kevin Bacon number

Problem Solving Strategy

To solve the problem, we will follow these steps:

Store people and relationships in the form of a graph based on the input.
Use Dijkstra’s algorithm or BFS (Breadth First Search) to calculate each person’s Kevin Bacon number.
Compare all people’s Kevin Bacon numbers and print the ID of the person with the smallest number.

Code Implementation

We will implement this problem in Kotlin.


import java.util.*

fun main() {
    val reader = Scanner(System.`in`)
    val n = reader.nextInt() // Number of people
    val m = reader.nextInt() // Number of relationships

    // Initialize adjacency list
    val graph = Array(n + 1) { mutableListOf() }

    // Receive relationships input
    for (i in 0 until m) {
        val u = reader.nextInt()
        val v = reader.nextInt()
        graph[u].add(v)
        graph[v].add(u)
    }

    // Array to store each person's Kevin Bacon number
    val kevinBaconScores = IntArray(n + 1)

    // Define BFS method
    fun bfs(start: Int) {
        val queue: Queue> = LinkedList()
        val visited = BooleanArray(n + 1)
        queue.add(Pair(start, 0)) // Starting person with distance 0
        visited[start] = true

        while (queue.isNotEmpty()) {
            val (current, distance) = queue.poll()
            for (neighbor in graph[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true
                    queue.add(Pair(neighbor, distance + 1))
                    kevinBaconScores[start] += distance + 1 // Calculate Kevin Bacon score
                }
            }
        }
    }

    // Perform BFS for all people
    for (i in 1..n) {
        bfs(i)
    }

    // Find the person with the minimum Kevin Bacon number
    var minScore = Int.MAX_VALUE
    var resultId = -1
    
    for (i in 1..n) {
        if (kevinBaconScores[i] < minScore) {
            minScore = kevinBaconScores[i]
            resultId = i
        }
    }

    // Print the result
    println(resultId)
}

Process Description

First, we input the number of people (n) and relationships (m) to create the graph, storing the relationships in adjacency list form. Then, we use the BFS algorithm to calculate each person’s Kevin Bacon number. BFS explores all connected individuals starting from each person, increasing the distance and ultimately recording each person’s Kevin Bacon score.

Finally, we compare all individuals’ Kevin Bacon scores to find the smallest value. In case of a tie, the person with the smaller ID is chosen.

Conclusion

Through this course, we learned how to solve algorithm problems using Kevin Bacon’s Six Degrees of Separation. Understanding graph theory and the BFS algorithm is very useful for technical interviews. Practice these problems extensively to prepare effectively for coding tests.

Kotlin Coding Test Course, Kevin Bacon’s Six Degrees of Separation