{"id":34940,"date":"2024-11-01T09:33:50","date_gmt":"2024-11-01T09:33:50","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34940"},"modified":"2024-11-01T12:55:29","modified_gmt":"2024-11-01T12:55:29","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b0%80%ec%9e%a5-%eb%b9%a0%eb%a5%b8-%eb%b2%84%ec%8a%a4-%eb%85%b8%ec%84%a0-%ea%b5%ac%ed%95%98%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34940\/","title":{"rendered":"Kotlin coding test course, finding the fastest bus route"},"content":{"rendered":"

<\/p>\n

As part of the coding test course using Kotlin, we will tackle the problem of finding the fastest bus route. In modern society, public transportation is an important means of transportation, and understanding the travel routes by bus is a feature that many people need. In this problem, we will design and implement an algorithm that calculates the shortest time according to the given conditions.<\/p>\n

Problem Definition<\/h2>\n

Several bus routes are given as follows. Each route includes a starting station, an arrival station, and the time taken. Your goal is to find the fastest time taken from a specific starting station to a specific arrival station.<\/p>\n

Problem Input<\/h3>\n
\n- Number of stations N (1 \u2264 N \u2264 100)\n- Number of routes M (1 \u2264 M \u2264 1000)\n- Each route information: starting station A, arrival station B, time taken T (1 \u2264 A, B \u2264 N, 1 \u2264 T \u2264 1000)\n- Starting station S and arrival station D\n<\/pre>\n
Problem Output<\/h3>\n
\n- The fastest time taken to go from the starting station to the arriving station. Output -1 if it is impossible.\n<\/pre>\n
Problem Solving Strategy<\/h2>\n
This problem is about finding the shortest path, and an appropriate algorithm to use is Dijkstra’s shortest path algorithm. The Dijkstra algorithm is useful for finding the shortest path from a starting vertex to all other vertices in a weighted graph. We will build a graph using the bus route information and use that graph to calculate the shortest time.<\/p>\n
Step-by-Step Approach<\/h3>\n
Step 1: Define Input Data Structure<\/h4>\n
First, based on the provided route information, we will decide how to represent the graph. It is efficient to manage each station’s associated route information using an adjacency list.<\/p>\n
\nval graph: Array>> = Array(N + 1) { mutableListOf() }\n<\/pre>\n
Step 2: Process Input Data<\/h4>\n
Convert the route information received from the user into graph form. Add each route information to the graph in the appropriate format.<\/p>\n
\nfor (i in 0 until M) {\n    val (A, B, T) = readLine()!!.split(\" \").map { it.toInt() }\n    graph[A].add(Pair(B, T))\n}\n<\/pre>\n
Step 3: Implement Dijkstra’s Algorithm<\/h4>\n
Use Dijkstra’s algorithm to calculate the shortest path for all stations. A priority queue is used to process the route with the least current time first.<\/p>\n
\nfun dijkstra(start: Int): IntArray {\n    val distances = IntArray(N + 1) { Int.MAX_VALUE }\n    distances[start] = 0\n    val priorityQueue = PriorityQueue>(compareBy { it.second })\n    priorityQueue.add(Pair(start, 0))\n\n    while (priorityQueue.isNotEmpty()) {\n        val (currentStation, currentTime) = priorityQueue.poll()\n\n        if (currentTime > distances[currentStation]) continue\n\n        for (edge in graph[currentStation]) {\n            val (nextStation, travelTime) = edge\n            val newTime = currentTime + travelTime\n\n            if (newTime < distances[nextStation]) {\n                distances[nextStation] = newTime\n                priorityQueue.add(Pair(nextStation, newTime))\n            }\n        }\n    }\n    return distances\n}\n<\/pre>\n
Step 4: Output Result<\/h4>\n
Finally, output the shortest time taken to go from the starting station to the arrival station. If it is not possible to reach the arrival station, output -1.<\/p>\n
\nval distances = dijkstra(S)\nprintln(if (distances[D] == Int.MAX_VALUE) -1 else distances[D])\n<\/pre>\n
Complete Code Example<\/h2>\n
\nfun main() {\n    val (N, M) = readLine()!!.split(\" \").map { it.toInt() }\n    val graph: Array>> = Array(N + 1) { mutableListOf() }\n\n    for (i in 0 until M) {\n        val (A, B, T) = readLine()!!.split(\" \").map { it.toInt() }\n        graph[A].add(Pair(B, T))\n    }\n\n    val (S, D) = readLine()!!.split(\" \").map { it.toInt() }\n    val distances = dijkstra(S)\n\n    println(if (distances[D] == Int.MAX_VALUE) -1 else distances[D])\n}\n\nfun dijkstra(start: Int): IntArray {\n    val distances = IntArray(N + 1) { Int.MAX_VALUE }\n    distances[start] = 0\n    val priorityQueue = PriorityQueue>(compareBy { it.second })\n    priorityQueue.add(Pair(start, 0))\n\n    while (priorityQueue.isNotEmpty()) {\n        val (currentStation, currentTime) = priorityQueue.poll()\n\n        if (currentTime > distances[currentStation]) continue\n\n        for (edge in graph[currentStation]) {\n            val (nextStation, travelTime) = edge\n            val newTime = currentTime + travelTime\n\n            if (newTime < distances[nextStation]) {\n                distances[nextStation] = newTime\n                priorityQueue.add(Pair(nextStation, newTime))\n            }\n        }\n    }\n    return distances\n}\n<\/pre>\n
Conclusion<\/h2>\n
In this lecture, we solved the problem of choosing the fastest bus route using Kotlin. We learned how to address the shortest path problem through the Dijkstra algorithm and how to implement the various elements of the problem in code. Algorithm problems can improve through practice, so it is recommended to continuously try solving various problems.<\/p>\n
\nNote:<\/strong> This problem requires an understanding of graph theory, and it is also advisable to practice other shortest path algorithms like the Bellman-Ford algorithm.\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
As part of the coding test course using Kotlin, we will tackle the problem of finding the fastest bus route. In modern society, public transportation is an important means of transportation, and understanding the travel routes by bus is a feature that many people need. In this problem, we will design and implement an algorithm … \ub354 \ubcf4\uae30 “Kotlin coding test course, finding the fastest bus route”<\/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-34940","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"\nKotlin coding test course, finding the fastest bus route - \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\/34940\/\" \/>\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, finding the fastest bus route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"As part of the coding test course using Kotlin, we will tackle the problem of finding the fastest bus route. In modern society, public transportation is an important means of transportation, and understanding the travel routes by bus is a feature that many people need. In this problem, we will design and implement an algorithm … \ub354 \ubcf4\uae30 "Kotlin coding test course, finding the fastest bus route"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34940\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:33:50+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T12:55:29+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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin coding test course, finding the fastest bus route\",\"datePublished\":\"2024-11-01T09:33:50+00:00\",\"dateModified\":\"2024-11-01T12:55:29+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/\"},\"wordCount\":393,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34940\/\",\"name\":\"Kotlin coding test course, finding the fastest bus route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:33:50+00:00\",\"dateModified\":\"2024-11-01T12:55:29+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34940\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34940\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Kotlin coding test course, finding the fastest bus route\"}]},{\"@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, finding the fastest bus route - \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\/34940\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin coding test course, finding the fastest bus route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"As part of the coding test course using Kotlin, we will tackle the problem of finding the fastest bus route. In modern society, public transportation is an important means of transportation, and understanding the travel routes by bus is a feature that many people need. In this problem, we will design and implement an algorithm … \ub354 \ubcf4\uae30 \"Kotlin coding test course, finding the fastest bus route\"","og_url":"https:\/\/atmokpo.com\/w\/34940\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:33:50+00:00","article_modified_time":"2024-11-01T12:55:29+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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34940\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34940\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin coding test course, finding the fastest bus route","datePublished":"2024-11-01T09:33:50+00:00","dateModified":"2024-11-01T12:55:29+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34940\/"},"wordCount":393,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34940\/","url":"https:\/\/atmokpo.com\/w\/34940\/","name":"Kotlin coding test course, finding the fastest bus route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:33:50+00:00","dateModified":"2024-11-01T12:55:29+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34940\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34940\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34940\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Kotlin coding test course, finding the fastest bus route"}]},{"@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\/34940","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=34940"}],"version-history":[{"count":2,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34940\/revisions"}],"predecessor-version":[{"id":38119,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34940\/revisions\/38119"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}