\n\n The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development.
\n It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate
\n the ability to solve various problems. Today, we will look into the maze exploration problem. To solve this problem, we will compare
\n the Depth-First Search (DFS) algorithm and the Breadth-First Search (BFS) algorithm.\n <\/p>\n
Problem Definition<\/h2>\n
\n The problem is to find the shortest path from the starting point to the destination in a maze represented by a given 2D array.
\n The maze consists of 0s and 1s, where 0 represents a traversable space and 1 represents a wall.
\n The starting point is (0, 0) and the destination is (n-1, m-1).
\n Here is an example maze:\n <\/p>\n
\n 0 0 1 0 0\n 1 0 1 0 1\n 0 0 0 0 1\n 0 1 1 0 0\n 0 0 0 0 0\n <\/pre>\nInput Format<\/h2>\n
\n A 2D array of size n x m is inputted. The array consists of 0s and 1s.\n <\/p>\n
Output Format<\/h2>\n
\n The length of the shortest path from the starting point to the destination is outputted. If it is not reachable, -1 is outputted.\n <\/p>\n
Approach to Solve the Problem<\/h2>\n
\n Various search algorithms can be used to solve this problem. Among them,
\n Depth-First Search (DFS) and Breadth-First Search (BFS) are the most commonly used.
\n BFS is suitable for shortest path problems. I will provide a brief explanation of each algorithm.\n <\/p>\n
BFS (Breadth-First Search)<\/h3>\n
\n BFS visits all vertices of a graph level by level. It visits all adjacent vertices from the starting vertex,
\n then explores adjacent vertices in the next step to explore all paths. BFS is implemented using a queue,
\n and it can find the shortest path by recording the depth of the path each time a vertex is visited. The time complexity of BFS is O(V + E).\n <\/p>\n
DFS (Depth-First Search)<\/h3>\n
\n DFS starts at one vertex of the graph and explores as deeply as possible before backtracking to explore alternative paths.
\n DFS is implemented using a stack, and the order of visiting depends on the depth. Since DFS explores all paths, it does not guarantee
\n the shortest path. Therefore, BFS is more suitable for maze exploration problems. The time complexity of DFS is O(V + E),
\n and its space complexity is O(V).\n <\/p>\n
Algorithm Design<\/h3>\n
\n Now, let’s design an algorithm to solve the maze exploration problem using BFS.
\n We need to define and initialize the necessary variables to proceed to the next steps.\n <\/p>\n
\n \/\/ maze size n, m\n let n = maze.count\n let m = maze[0].count\n \/\/ direction array (up, down, left, right)\n let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n var queue: [(Int, Int)] = []\n \/\/ add starting point (0, 0) to queue\n queue.append((0, 0))\n \/\/ visited array\n var visited = Array(repeating: Array(repeating: false, count: m), count: n)\n visited[0][0] = true\n \/\/ distance array\n var distance = Array(repeating: Array(repeating: -1, count: m), count: n)\n distance[0][0] = 0\n <\/pre>\nCode Implementation<\/h2>\n
\n Let’s solve the problem with code. Below is the BFS algorithm implemented in Swift.\n <\/p>\n
\n func bfs(maze: [[Int]]) -> Int {\n let n = maze.count\n let m = maze[0].count\n let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n var queue: [(Int, Int)] = []\n var visited = Array(repeating: Array(repeating: false, count: m), count: n)\n var distance = Array(repeating: Array(repeating: -1, count: m), count: n)\n \n queue.append((0, 0))\n visited[0][0] = true\n distance[0][0] = 0\n \n while !queue.isEmpty {\n let (x, y) = queue.removeFirst()\n \n for direction in directions {\n let newX = x + direction.0\n let newY = y + direction.1\n \n if newX >= 0 && newY >= 0 && newX < n && newY < m &&\n maze[newX][newY] == 0 && !visited[newX][newY] {\n visited[newX][newY] = true\n distance[newX][newY] = distance[x][y] + 1\n queue.append((newX, newY))\n }\n }\n }\n \n return distance[n-1][m-1] != -1 ? distance[n-1][m-1] : -1\n }\n\n let maze = [\n [0, 0, 1, 0, 0],\n [1, 0, 1, 0, 1],\n [0, 0, 0, 0, 1],\n [0, 1, 1, 0, 0],\n [0, 0, 0, 0, 0]\n ]\n\n let result = bfs(maze: maze)\n print(result) \/\/ Result: 8\n <\/pre>\nCode Explanation<\/h2>\n
\n In the above code, we used the BFS algorithm to explore the maze and find the shortest path.
\n Initially, we start at the coordinate (0, 0), and set up the queue, visited array, and distance array.
\n When we dequeue one coordinate from the queue, we check all adjacent coordinates. If it is a traversable coordinate, we add it to the queue and update the
\n visited array and distance array. Finally, we return the distance value of the destination point.
\n If it is unreachable, we return -1.\n <\/p>\n
Conclusion<\/h2>\n
\n In this tutorial, we learned how to solve the maze exploration problem with Swift.
\n Through the BFS algorithm, we effectively utilized the queue and dimensional arrays to find the shortest path.
\n Such search algorithms are often encountered in job interviews, so we need to practice sufficiently to solve a variety of problems.
\n These fundamental concepts are very useful when solving algorithm problems in Swift.\n <\/p>\n<\/article>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development. It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate the ability to solve various problems. Today, we will look into the maze exploration problem. … \ub354 \ubcf4\uae30 “Swift Coding Test Course, Exploring a Maze”<\/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-34726","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"\nSwift Coding Test Course, Exploring a Maze - \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\/34726\/\" \/>\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, Exploring a Maze - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development. It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate the ability to solve various problems. Today, we will look into the maze exploration problem. … \ub354 \ubcf4\uae30 "Swift Coding Test Course, Exploring a Maze"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34726\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:31:19+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:49+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=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Exploring a Maze\",\"datePublished\":\"2024-11-01T09:31:19+00:00\",\"dateModified\":\"2024-11-01T11:26:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/\"},\"wordCount\":569,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34726\/\",\"name\":\"Swift Coding Test Course, Exploring a Maze - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:31:19+00:00\",\"dateModified\":\"2024-11-01T11:26:49+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34726\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34726\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Exploring a Maze\"}]},{\"@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, Exploring a Maze - \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\/34726\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Exploring a Maze - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development. It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate the ability to solve various problems. Today, we will look into the maze exploration problem. … \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Exploring a Maze\"","og_url":"https:\/\/atmokpo.com\/w\/34726\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:31:19+00:00","article_modified_time":"2024-11-01T11:26:49+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":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34726\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34726\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Exploring a Maze","datePublished":"2024-11-01T09:31:19+00:00","dateModified":"2024-11-01T11:26:49+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34726\/"},"wordCount":569,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34726\/","url":"https:\/\/atmokpo.com\/w\/34726\/","name":"Swift Coding Test Course, Exploring a Maze - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:31:19+00:00","dateModified":"2024-11-01T11:26:49+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34726\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34726\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34726\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Exploring a Maze"}]},{"@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\/34726","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=34726"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34726\/revisions"}],"predecessor-version":[{"id":34727,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34726\/revisions\/34727"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}