\n The first line contains the number of cities, n. The following n lines contain the distance matrix between cities.
\n The distance matrix is constructed as follows:\n <\/p>\n
\n
\n 0 10 15 20\n 10 0 35 25\n 15 35 0 30\n 20 25 30 0\n <\/pre>\n<\/div>\n\n In the example above, the first line indicates there are 4 cities, and it represents the distances between each city.
\n For example, the distance between city 1 and city 2 is 10, and the distance between city 1 and city 3 is 15.\n <\/p>\n
Output Format<\/h2>\n
\n Print the total distance of the minimum route.\n <\/p>\n
Problem Solving Approach<\/h2>\n
\n This problem can be approached in various ways, but here we will describe a method using backtracking<\/strong> and dynamic programming (DP)<\/strong>.
\n While backtracking can be used to explore all routes and find the minimum path, the computational workload increases exponentially as the number of cities grows.
\n Therefore, combining dynamic programming with memoization can enhance efficiency.\n <\/p>\nAlgorithm Implementation<\/h2>\n
\n Initially, we can implement the solution by generating all possible paths using backtracking with permutations, and then calculating the distance of each path to update the minimum value.
\n Below is an example code implemented in Swift.\n <\/p>\n
\n
\n func tsp(graph: [[Int]], visited: inout [Bool], currentIndex: Int, count: Int, cost: Int, ans: inout Int) {\n \/\/ If all cities have been visited\n if count == graph.count && graph[currentIndex][0] > 0 {\n ans = min(ans, cost + graph[currentIndex][0])\n return\n }\n for i in 0.. 0 {\n visited[i] = true\n tsp(graph: graph, visited: &visited, currentIndex: i, count: count + 1, cost: cost + graph[currentIndex][i], ans: &ans)\n visited[i] = false\n }\n }\n }\n\n func findMinCost(graph: [[Int]]) -> Int {\n var visited = [Bool](repeating: false, count: graph.count)\n var ans = Int.max\n visited[0] = true\n tsp(graph: graph, visited: &visited, currentIndex: 0, count: 1, cost: 0, ans: &ans)\n return ans\n }\n\n let graph = [\n [0, 10, 15, 20],\n [10, 0, 35, 25],\n [15, 35, 0, 30],\n [20, 25, 30, 0]\n ]\n\n let result = findMinCost(graph: graph)\n print(\"Distance of the minimum route: \\(result)\")\n <\/graph.count><\/pre>\n<\/div>\nCode Explanation<\/h2>\n
\n The code above is structured as follows:\n <\/p>\n
\n- \ntsp Function<\/strong>: Recursively explores all paths visiting the cities,
\n traversing all unvisited cities from the current city. If the cost of visiting a city is minimal,
\n it updates the minimum cost of the current path.\n <\/li>\n- \nfindMinCost Function<\/strong>: Acts as an initializer and calls the tsp function
\n while visiting the first city (0) to explore the entire path.\n <\/li>\n<\/ul>\nComplexity Analysis<\/h2>\n
\n The time complexity of this algorithm is O(n!). This is because it has to traverse each city and explore all paths.
\n It can be used when n is small, but it becomes inefficient as n increases.
\n Therefore, for more efficient methods, dynamic programming can be applied using bit masking to reduce complexity.
\n This method has a time complexity of O(n^2 * 2^n) and is practical for n below 20.\n <\/p>\n
Conclusion<\/h2>\n
\n The ‘Salesman\u2019s Dilemma’ problem is closely related to various optimization problems in reality and provides important insights when solving problems through effective algorithm design.
\n By tackling problems like this while preparing for coding tests, one can enhance their understanding of graph algorithms and dynamic programming, as well as develop systematic problem-solving skills.\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Problem Definition The ‘Salesman\u2019s Dilemma’ problem seeks to find the minimum route for a salesman to visit all given cities once and return to the starting city, based on the distance information between the cities. This is an optimization problem known as the Traveling Salesman Problem (TSP), which is a form of graph theory. This … \ub354 \ubcf4\uae30 “Swift Coding Test Course, Salesman’s Concerns”<\/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":[129],"tags":[],"class_list":["post-34764","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"\nSwift Coding Test Course, Salesman's Concerns - \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\/34764\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Swift Coding Test Course, Salesman's Concerns - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Definition The ‘Salesman\u2019s Dilemma’ problem seeks to find the minimum route for a salesman to visit all given cities once and return to the starting city, based on the distance information between the cities. This is an optimization problem known as the Traveling Salesman Problem (TSP), which is a form of graph theory. This … \ub354 \ubcf4\uae30 "Swift Coding Test Course, Salesman’s Concerns"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34764\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:31:44+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:38+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\/34764\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34764\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Salesman’s Concerns\",\"datePublished\":\"2024-11-01T09:31:44+00:00\",\"dateModified\":\"2024-11-01T11:26:38+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34764\/\"},\"wordCount\":493,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34764\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34764\/\",\"name\":\"Swift Coding Test Course, Salesman's Concerns - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:31:44+00:00\",\"dateModified\":\"2024-11-01T11:26:38+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34764\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34764\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34764\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Salesman’s Concerns\"}]},{\"@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":"Swift Coding Test Course, Salesman's Concerns - \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\/34764\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Salesman's Concerns - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Definition The ‘Salesman\u2019s Dilemma’ problem seeks to find the minimum route for a salesman to visit all given cities once and return to the starting city, based on the distance information between the cities. This is an optimization problem known as the Traveling Salesman Problem (TSP), which is a form of graph theory. This … \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Salesman’s Concerns\"","og_url":"https:\/\/atmokpo.com\/w\/34764\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:31:44+00:00","article_modified_time":"2024-11-01T11:26:38+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\/34764\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34764\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Salesman’s Concerns","datePublished":"2024-11-01T09:31:44+00:00","dateModified":"2024-11-01T11:26:38+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34764\/"},"wordCount":493,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34764\/","url":"https:\/\/atmokpo.com\/w\/34764\/","name":"Swift Coding Test Course, Salesman's Concerns - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:31:44+00:00","dateModified":"2024-11-01T11:26:38+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34764\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34764\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34764\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Salesman’s Concerns"}]},{"@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\/34764","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=34764"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34764\/revisions"}],"predecessor-version":[{"id":34765,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34764\/revisions\/34765"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}