{"id":35158,"date":"2024-11-01T09:36:12","date_gmt":"2024-11-01T09:36:12","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35158"},"modified":"2024-11-01T11:44:48","modified_gmt":"2024-11-01T11:44:48","slug":"kotlin-coding-test-course-kevin-bacons-six-degrees-of-separation","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35158\/","title":{"rendered":"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation"},"content":{"rendered":"<p>In this course, we will explore &#8216;Kevin Bacon&#8217;s Six Degrees of Separation&#8217; and examine the process of solving related algorithm problems. Kevin Bacon&#8217;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.<\/p>\n<h2>Problem Description<\/h2>\n<pre>\n<p>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:<\/p>\n\n<p><strong>Problem: Kevin Bacon's Six Degrees of Separation<\/strong><\/p>\n<ul>\n    <li>Given n people and m relationships.<\/li>\n    <li>People are represented by integers from 1 to n.<\/li>\n    <li>Each relationship is given by the IDs of two people, indicating that they are friends.<\/li>\n    <li>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.<\/li>\n    <li>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.<\/li>\n<\/ul>\n<\/pre>\n<h2>Input Format<\/h2>\n<pre>\n<n> <m> \nID1 ID2\nID1 ID3\n...\n<\/m><\/n><\/pre>\n<h2>Output Format<\/h2>\n<pre>\nThe ID of the person with the smallest Kevin Bacon number\n<\/pre>\n<h2>Problem Solving Strategy<\/h2>\n<p>To solve the problem, we will follow these steps:<\/p>\n<ol>\n<li>Store people and relationships in the form of a graph based on the input.<\/li>\n<li>Use Dijkstra&#8217;s algorithm or BFS (Breadth First Search) to calculate each person&#8217;s Kevin Bacon number.<\/li>\n<li>Compare all people&#8217;s Kevin Bacon numbers and print the ID of the person with the smallest number.<\/li>\n<\/ol>\n<h2>Code Implementation<\/h2>\n<p>We will implement this problem in Kotlin.<\/p>\n<pre>\n<code>\nimport java.util.*\n\nfun main() {\n    val reader = Scanner(System.`in`)\n    val n = reader.nextInt() \/\/ Number of people\n    val m = reader.nextInt() \/\/ Number of relationships\n\n    \/\/ Initialize adjacency list\n    val graph = Array(n + 1) { mutableListOf<int>() }\n\n    \/\/ Receive relationships input\n    for (i in 0 until m) {\n        val u = reader.nextInt()\n        val v = reader.nextInt()\n        graph[u].add(v)\n        graph[v].add(u)\n    }\n\n    \/\/ Array to store each person's Kevin Bacon number\n    val kevinBaconScores = IntArray(n + 1)\n\n    \/\/ Define BFS method\n    fun bfs(start: Int) {\n        val queue: Queue<pair<int, int=\"\">&gt; = LinkedList()\n        val visited = BooleanArray(n + 1)\n        queue.add(Pair(start, 0)) \/\/ Starting person with distance 0\n        visited[start] = true\n\n        while (queue.isNotEmpty()) {\n            val (current, distance) = queue.poll()\n            for (neighbor in graph[current]) {\n                if (!visited[neighbor]) {\n                    visited[neighbor] = true\n                    queue.add(Pair(neighbor, distance + 1))\n                    kevinBaconScores[start] += distance + 1 \/\/ Calculate Kevin Bacon score\n                }\n            }\n        }\n    }\n\n    \/\/ Perform BFS for all people\n    for (i in 1..n) {\n        bfs(i)\n    }\n\n    \/\/ Find the person with the minimum Kevin Bacon number\n    var minScore = Int.MAX_VALUE\n    var resultId = -1\n    \n    for (i in 1..n) {\n        if (kevinBaconScores[i] &lt; minScore) {\n            minScore = kevinBaconScores[i]\n            resultId = i\n        }\n    }\n\n    \/\/ Print the result\n    println(resultId)\n}\n<\/pair<int,><\/int><\/code>\n<\/pre>\n<h2>Process Description<\/h2>\n<p>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&#8217;s Kevin Bacon number. BFS explores all connected individuals starting from each person, increasing the distance and ultimately recording each person&#8217;s Kevin Bacon score.<\/p>\n<p>Finally, we compare all individuals&#8217; Kevin Bacon scores to find the smallest value. In case of a tie, the person with the smaller ID is chosen.<\/p>\n<h2>Conclusion<\/h2>\n<p>Through this course, we learned how to solve algorithm problems using Kevin Bacon&#8217;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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this course, we will explore &#8216;Kevin Bacon&#8217;s Six Degrees of Separation&#8217; and examine the process of solving related algorithm problems. Kevin Bacon&#8217;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 &hellip; <a href=\"https:\/\/atmokpo.com\/w\/35158\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[106],"tags":[],"class_list":["post-35158","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Kotlin Coding Test Course, Kevin Bacon&#039;s Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/35158\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Kotlin Coding Test Course, Kevin Bacon&#039;s Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this course, we will explore &#8216;Kevin Bacon&#8217;s Six Degrees of Separation&#8217; and examine the process of solving related algorithm problems. Kevin Bacon&#8217;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 &hellip; \ub354 \ubcf4\uae30 &quot;Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35158\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:36:12+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:44:48+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation\",\"datePublished\":\"2024-11-01T09:36:12+00:00\",\"dateModified\":\"2024-11-01T11:44:48+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/\"},\"wordCount\":266,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35158\/\",\"name\":\"Kotlin Coding Test Course, Kevin Bacon's Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:36:12+00:00\",\"dateModified\":\"2024-11-01T11:44:48+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35158\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35158\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Kotlin Coding Test Course, Kevin Bacon's Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/35158\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin Coding Test Course, Kevin Bacon's Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this course, we will explore &#8216;Kevin Bacon&#8217;s Six Degrees of Separation&#8217; and examine the process of solving related algorithm problems. Kevin Bacon&#8217;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 &hellip; \ub354 \ubcf4\uae30 \"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation\"","og_url":"https:\/\/atmokpo.com\/w\/35158\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:36:12+00:00","article_modified_time":"2024-11-01T11:44:48+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/35158\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35158\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation","datePublished":"2024-11-01T09:36:12+00:00","dateModified":"2024-11-01T11:44:48+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35158\/"},"wordCount":266,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35158\/","url":"https:\/\/atmokpo.com\/w\/35158\/","name":"Kotlin Coding Test Course, Kevin Bacon's Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:36:12+00:00","dateModified":"2024-11-01T11:44:48+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35158\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35158\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35158\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Kotlin Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35158","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=35158"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35158\/revisions"}],"predecessor-version":[{"id":35159,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35158\/revisions\/35159"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}