Hello, in this lecture, we will learn how to solve the pathfinding problem using the Swift language. Pathfinding is one of the common types of problems that often appear in coding tests, where the task is to find a path between two specific nodes in a given graph. In this article, we will define the problem and thoroughly discuss the algorithms and data structures needed to solve it.<\/p>\n
\nProblem:<\/strong> Write a function to determine whether there exists a path between two nodes A and B in a given directed graph. The graph is provided in the form of an adjacency list, with nodes and edges represented as integers.<\/p>\n<\/blockquote>\nInput:<\/strong><\/p>\n\n- Integer N: the number of nodes (1 \u2264 N \u2264 1000)<\/li>\n
- Integer M: the number of edges (1 \u2264 M \u2264 10000)<\/li>\n
- Length of the list M: each edge indicates a direction from node u to node v in the form [u, v].<\/li>\n
- Integer A, B: the starting node A and the ending node B to check for a path.<\/li>\n<\/ul>\n
Output:<\/strong><\/p>\n\n- If there exists a path from node A to node B, print “YES”; if not, print “NO”.<\/li>\n<\/ul>\n
Problem Analysis<\/h2>\n
This problem falls under the category of ‘path search’ in graph theory and can be solved using various methods. You can explore paths using DFS (Depth-First Search) or BFS (Breadth-First Search), both of which can effectively explore graphs in the form of adjacency lists.<\/p>\n
Algorithm Selection<\/h2>\n
In this lecture, we will use BFS to explore the graph. BFS is an algorithm that uses a queue to explore each node level by level, making it advantageous for finding the shortest path. We will check if we can reach the destination node through graph traversal.<\/p>\n
Swift Code Implementation<\/h2>\n
Now, let’s write the actual Swift code. Below is an example of a pathfinding function that uses BFS.<\/p>\n
\n \n import Foundation\n\n func canReach(start: Int, end: Int, edges: [[Int]], nodeCount: Int) -> String {\n var adjacencyList = [[Int]](repeating: [Int](), count: nodeCount + 1)\n for edge in edges {\n adjacencyList[edge[0]].append(edge[1])\n }\n\n var queue = [start]\n var visited = [Bool](repeating: false, count: nodeCount + 1)\n visited[start] = true\n\n while !queue.isEmpty {\n let current = queue.removeFirst()\n\n if current == end {\n return \"YES\"\n }\n\n for neighbor in adjacencyList[current] {\n if !visited[neighbor] {\n visited[neighbor] = true\n queue.append(neighbor)\n }\n }\n }\n return \"NO\"\n }\n\n \/\/ Example input\n let nodeCount = 6\n let edges = [[1, 2], [1, 3], [2, 4], [4, 5], [3, 6]]\n let start = 1\n let end = 5\n\n print(canReach(start: start, end: end, edges: edges, nodeCount: nodeCount))\n <\/code>\n <\/pre>\nCode Explanation<\/h2>\n
Analyzing the above code, it consists of the following steps:<\/p>\n
\n- Create a graph in the form of an adjacency list. Store connected nodes for each node.<\/li>\n
- Initialize a queue for BFS traversal and mark the starting node as visited.<\/li>\n
- Repeat the following process until the queue is empty:\n
\n- Take a node from the front of the queue.<\/li>\n
- If the taken node is the destination node, return “YES”.<\/li>\n
- For all adjacent nodes of the current node, add unvisited nodes to the queue and mark them as visited.<\/li>\n<\/ul>\n<\/li>\n
- If the queue is empty but the target node has not been reached, return “NO”.<\/li>\n<\/ol>\n
Complexity Analysis<\/h2>\n
The time complexity of the BFS algorithm is O(V + E), where V is the number of nodes and E is the number of edges. Considering the maximum conditions given in this problem, it is very efficient. The memory complexity also requires O(V + E) to store the adjacency list.<\/p>\n
Testing and Applications<\/h2>\n
The given function can be applied to various graph structures and tested accordingly. Let’s look at a few additional test cases.<\/p>\n
\n \n \/\/ Additional test cases\n let additionalEdges1 = [[1, 2], [2, 3], [3, 4], [4, 5]]\n let additionalEdges2 = [[1, 2], [2, 3], [3, 4], [2, 5]]\n \n print(canReach(start: 1, end: 5, edges: additionalEdges1, nodeCount: nodeCount)) \/\/ NO\n print(canReach(start: 1, end: 5, edges: additionalEdges2, nodeCount: nodeCount)) \/\/ YES\n <\/code>\n <\/pre>\nConclusion<\/h2>\n
In this lecture, we learned how to solve the pathfinding problem in graphs using Swift. We effectively solved the problem using the BFS algorithm, which is very important in coding tests. When encountering similar problems in practice, you will be able to solve them based on the knowledge gained from this lecture.<\/p>\n
Now it\u2019s your turn to tackle various graph problems and enhance your algorithm skills. Keep practicing!<\/p>\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Hello, in this lecture, we will learn how to solve the pathfinding problem using the Swift language. Pathfinding is one of the common types of problems that often appear in coding tests, where the task is to find a path between two specific nodes in a given graph. In this article, we will define the … \ub354 \ubcf4\uae30 “Swift Coding Test Course, Pathfinding”<\/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-34678","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"\nSwift Coding Test Course, Pathfinding - \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\/34678\/\" \/>\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, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, in this lecture, we will learn how to solve the pathfinding problem using the Swift language. Pathfinding is one of the common types of problems that often appear in coding tests, where the task is to find a path between two specific nodes in a given graph. In this article, we will define the … \ub354 \ubcf4\uae30 "Swift Coding Test Course, Pathfinding"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34678\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:30:47+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:27:01+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\/34678\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34678\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Pathfinding\",\"datePublished\":\"2024-11-01T09:30:47+00:00\",\"dateModified\":\"2024-11-01T11:27:01+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34678\/\"},\"wordCount\":559,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34678\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34678\/\",\"name\":\"Swift Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:30:47+00:00\",\"dateModified\":\"2024-11-01T11:27:01+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34678\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34678\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34678\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Pathfinding\"}]},{\"@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, Pathfinding - \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\/34678\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, in this lecture, we will learn how to solve the pathfinding problem using the Swift language. Pathfinding is one of the common types of problems that often appear in coding tests, where the task is to find a path between two specific nodes in a given graph. In this article, we will define the … \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Pathfinding\"","og_url":"https:\/\/atmokpo.com\/w\/34678\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:30:47+00:00","article_modified_time":"2024-11-01T11:27:01+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\/34678\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34678\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Pathfinding","datePublished":"2024-11-01T09:30:47+00:00","dateModified":"2024-11-01T11:27:01+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34678\/"},"wordCount":559,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34678\/","url":"https:\/\/atmokpo.com\/w\/34678\/","name":"Swift Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:30:47+00:00","dateModified":"2024-11-01T11:27:01+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34678\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34678\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34678\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Pathfinding"}]},{"@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\/34678","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=34678"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34678\/revisions"}],"predecessor-version":[{"id":34679,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34678\/revisions\/34679"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34678"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34678"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34678"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}