{"id":33520,"date":"2024-11-01T09:17:24","date_gmt":"2024-11-01T09:17:24","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33520"},"modified":"2024-11-01T11:38:08","modified_gmt":"2024-11-01T11:38:08","slug":"java-coding-test-course-kevin-bacons-six-degrees-of-separation","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33520\/","title":{"rendered":"Java Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation"},"content":{"rendered":"<div class=\"post\">\n<p>Hello! In this post, we will explore the &#8216;Six Degrees of Kevin Bacon&#8217; using Java. This law, derived from social network theory, suggests that any two people can be connected in six steps or less. We will transform this into an algorithm problem and implement it.<\/p>\n<h2>Problem Description<\/h2>\n<p>The problem we need to solve is as follows. Based on the given friendships represented as a graph, we need to find the shortest path between two specific people. By calculating the &#8220;Kevin Bacon Index&#8221; according to how connected these people are, we will discover who is connected to whom.<\/p>\n<h3>Problem Definition<\/h3>\n<p>When given a list of friendships, write an algorithm to calculate the &#8216;Kevin Bacon Index&#8217; for all people and find the person with the lowest index to print.<\/p>\n<h2>Input Format<\/h2>\n<ul>\n<li>The first line contains the number of people N (1 \u2264 N \u2264 1000).<\/li>\n<li>The next line contains the number of friendships M (0 \u2264 M \u2264 100,000).<\/li>\n<li>Then, M lines follow with two numbers A, B (1 \u2264 A, B \u2264 N) representing friendships. This means A and B are friends.<\/li>\n<\/ul>\n<h2>Output Format<\/h2>\n<p>Calculate the Kevin Bacon Index for all people and print the number of the person with the lowest value. If two people have the same Kevin Bacon Index, print the one with the smaller number.<\/p>\n<h2>Problem Solving Process<\/h2>\n<p>To solve this problem, we will follow the steps below:<\/p>\n<h3>Step 1: Graph Implementation<\/h3>\n<p>Friendships can be represented in the form of a graph. Each person is a vertex, and the friendships between two people are represented as edges. Here, we will implement the graph using an adjacency list.<\/p>\n<pre><code>\nimport java.util.*;\n\npublic class KevinBaconGame {\n    static List<List<Integer>> graph;\n    static int[] distance;\n\n    public static void main(String[] args) {\n        \/\/ Here, we will handle input and initialize the graph.\n    }\n}\n    <\/code><\/pre>\n<h3>Step 2: Implementing BFS Algorithm<\/h3>\n<p>We will use BFS to calculate the Kevin Bacon Index. BFS is very effective in finding the shortest path. By running BFS from each person, we can calculate the shortest paths to all friends.<\/p>\n<pre><code>\n    static int bfs(int start) {\n        Queue<Integer> queue = new LinkedList<>();\n        boolean[] visited = new boolean[graph.size()];\n        Arrays.fill(distance, Integer.MAX_VALUE);\n        \n        queue.offer(start);\n        visited[start] = true;\n        distance[start] = 0;\n\n        while (!queue.isEmpty()) {\n            int current = queue.poll();\n\n            for (int neighbor : graph.get(current)) {\n                if (!visited[neighbor]) {\n                    visited[neighbor] = true;\n                    distance[neighbor] = distance[current] + 1;\n                    queue.offer(neighbor);\n                }\n            }\n        }\n        \n        int totalDistance = 0;\n        for (int d : distance) {\n            totalDistance += d;\n        }\n        return totalDistance;\n    }\n    <\/code><\/pre>\n<h3>Step 3: Result Calculation and Output<\/h3>\n<p>Run BFS for all people, calculate the Kevin Bacon Index, and finally find the person with the lowest index. During this process, store and compare the person number and index.<\/p>\n<pre><code>\n    for (int i = 1; i <= N; i++) {\n        int baconIndex = bfs(i);\n        \/\/ Here, we will add logic to store the Kevin Bacon Index.\n    }\n    \/\/ Final result output part.\n    <\/code><\/pre>\n<h2>View Full Code<\/h2>\n<pre><code>\nimport java.util.*;\n\npublic class KevinBaconGame {\n    static List<List<Integer>> graph;\n    static int[] distance;\n\n    public static void main(String[] args) {\n        Scanner scanner = new Scanner(System.in);\n        int N = scanner.nextInt();\n        int M = scanner.nextInt();\n        \n        graph = new ArrayList<>();\n        distance = new int[N + 1];\n\n        for (int i = 0; i <= N; i++) {\n            graph.add(new ArrayList<>());\n        }\n\n        for (int i = 0; i < M; i++) {\n            int A = scanner.nextInt();\n            int B = scanner.nextInt();\n            graph.get(A).add(B);\n            graph.get(B).add(A);\n        }\n\n        int minBaconIndex = Integer.MAX_VALUE;\n        int resultPerson = 0;\n\n        for (int i = 1; i <= N; i++) {\n            int baconIndex = bfs(i);\n            if (baconIndex < minBaconIndex) {\n                minBaconIndex = baconIndex;\n                resultPerson = i;\n            }\n        }\n\n        System.out.println(resultPerson);\n    }\n\n    static int bfs(int start) {\n        Queue<Integer> queue = new LinkedList<>();\n        boolean[] visited = new boolean[graph.size()];\n        Arrays.fill(distance, Integer.MAX_VALUE);\n        \n        queue.offer(start);\n        visited[start] = true;\n        distance[start] = 0;\n\n        while (!queue.isEmpty()) {\n            int current = queue.poll();\n\n            for (int neighbor : graph.get(current)) {\n                if (!visited[neighbor]) {\n                    visited[neighbor] = true;\n                    distance[neighbor] = distance[current] + 1;\n                    queue.offer(neighbor);\n                }\n            }\n        }\n        \n        int totalDistance = 0;\n        for (int d : distance) {\n            totalDistance += d;\n        }\n        return totalDistance;\n    }\n}\n    <\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>In this post, we implemented an algorithm to check the relationships among friends based on Kevin Bacon's Six Degrees theory and to find the closest person using the Kevin Bacon Index. We learned how to effectively calculate the shortest path using BFS and navigate through the friendship graph. To gain deeper insights into solving coding test problems using Java, I recommend attempting similar algorithmic problems multiple times.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello! In this post, we will explore the &#8216;Six Degrees of Kevin Bacon&#8217; using Java. This law, derived from social network theory, suggests that any two people can be connected in six steps or less. We will transform this into an algorithm problem and implement it. Problem Description The problem we need to solve is &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33520\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Java 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":[139],"tags":[],"class_list":["post-33520","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Java 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\/33520\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, Kevin Bacon&#039;s Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this post, we will explore the &#8216;Six Degrees of Kevin Bacon&#8217; using Java. This law, derived from social network theory, suggests that any two people can be connected in six steps or less. We will transform this into an algorithm problem and implement it. Problem Description The problem we need to solve is &hellip; \ub354 \ubcf4\uae30 &quot;Java Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33520\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:17:24+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:38:08+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\/33520\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33520\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation\",\"datePublished\":\"2024-11-01T09:17:24+00:00\",\"dateModified\":\"2024-11-01T11:38:08+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33520\/\"},\"wordCount\":415,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33520\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33520\/\",\"name\":\"Java 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:17:24+00:00\",\"dateModified\":\"2024-11-01T11:38:08+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33520\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33520\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33520\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java 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":"Java 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\/33520\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Kevin Bacon's Six Degrees of Separation - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this post, we will explore the &#8216;Six Degrees of Kevin Bacon&#8217; using Java. This law, derived from social network theory, suggests that any two people can be connected in six steps or less. We will transform this into an algorithm problem and implement it. Problem Description The problem we need to solve is &hellip; \ub354 \ubcf4\uae30 \"Java Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation\"","og_url":"https:\/\/atmokpo.com\/w\/33520\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:17:24+00:00","article_modified_time":"2024-11-01T11:38:08+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\/33520\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33520\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Kevin Bacon&#8217;s Six Degrees of Separation","datePublished":"2024-11-01T09:17:24+00:00","dateModified":"2024-11-01T11:38:08+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33520\/"},"wordCount":415,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33520\/","url":"https:\/\/atmokpo.com\/w\/33520\/","name":"Java 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:17:24+00:00","dateModified":"2024-11-01T11:38:08+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33520\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33520\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33520\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java 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\/33520","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=33520"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33520\/revisions"}],"predecessor-version":[{"id":33521,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33520\/revisions\/33521"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}