{"id":34902,"date":"2024-11-01T09:33:23","date_gmt":"2024-11-01T09:33:23","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34902"},"modified":"2024-11-01T11:26:02","modified_gmt":"2024-11-01T11:26:02","slug":"swift-coding-test-course-finding-the-diameter-of-a-tree","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34902\/","title":{"rendered":"Swift Coding Test Course, Finding the Diameter of a Tree"},"content":{"rendered":"
\n

Solving various algorithm problems for coding test preparation is very helpful in improving your programming skills. This time, we will take a deep dive into the ‘Finding the Diameter of a Tree’ problem. Understanding and knowing how to solve tree structures is very useful, as they frequently appear in many programming problems.<\/p>\n

Problem Description<\/h2>\n

A tree is a non-linear data structure composed of nodes and edges. The diameter of a tree refers to the longest path between any two nodes in the tree. In other words, it is about finding the longest path between two nodes (the number of edges between the nodes). This problem can usually be solved using DFS (Depth-First Search) or BFS (Breadth-First Search).<\/p>\n

Problem Definition<\/h3>\n
\nGiven a tree, find the diameter of the tree.\nInput: Number of nodes N in the tree (1 <= N <= 100,000)\n      Edges in the form of N-1 pairs (u, v) representing each end node of the edge.\nOutput: Diameter of the tree\n    <\/pre>\n
Problem Analysis<\/h2>\n
Due to the nature of trees, where all nodes are connected by exactly one path, the method for finding the longest distance between two nodes is to explore using either DFS or BFS. The general idea is as follows:<\/p>\n
    \n
  1. Choose an arbitrary node A and find the node B that is farthest from A.<\/li>\n
  2. Then, find the node C that is farthest from B. The distance at this point is the diameter of the tree.<\/li>\n<\/ol>\n
    Algorithm Implementation<\/h2>\n
    Now let’s implement the above algorithm in Swift. We will use an adjacency list to represent the tree.<\/p>\n
    Swift Code Implementation<\/h3>\n
    \nimport Foundation\n\nclass Graph {\n    var adjList: [[Int]]\n\n    init(size: Int) {\n        adjList = Array(repeating: [], count: size)\n    }\n\n    func addEdge(u: Int, v: Int) {\n        adjList[u].append(v)\n        adjList[v].append(u)\n    }\n\n    func bfs(start: Int) -> (Int, Int) {\n        var dist = Array(repeating: -1, count: adjList.count)\n        var queue: [Int] = []\n        \n        dist[start] = 0\n        queue.append(start)\n\n        var farthestNode = start\n        var maxDistance = 0\n\n        while !queue.isEmpty {\n            let node = queue.removeFirst()\n            for neighbor in adjList[node] {\n                if dist[neighbor] == -1 { \/\/ If not visited\n                    dist[neighbor] = dist[node] + 1\n                    queue.append(neighbor)\n                    if dist[neighbor] > maxDistance {\n                        maxDistance = dist[neighbor]\n                        farthestNode = neighbor\n                    }\n                }\n            }\n        }\n        return (farthestNode, maxDistance)\n    }\n}\n\nfunc findTreeDiameter(edges: [(Int, Int)], n: Int) -> Int {\n    let graph = Graph(size: n)\n    for edge in edges {\n        graph.addEdge(u: edge.0 - 1, v: edge.1 - 1) \/\/ 0-indexed\n    }\n\n    let (farthestNode, _) = graph.bfs(start: 0)\n    let (_, diameter) = graph.bfs(start: farthestNode)\n    return diameter\n}\n\n\/\/ Example Input\nlet n = 5\nlet edges: [(Int, Int)] = [(1, 2), (1, 3), (2, 4), (2, 5)]\nlet diameter = findTreeDiameter(edges: edges, n: n)\nprint(\"Diameter of the tree: \\(diameter)\")\n    <\/code><\/pre>\n
    Code Explanation<\/h2>\n
    This code calculates the diameter of the tree in the following way:<\/p>\n
      \n
    1. First, we define a Graph class to store the edge list.<\/li>\n
    2. We add edge information using the addEdge method.<\/li>\n
    3. The bfs function performs BFS starting from a given node and returns the farthest node and its distance.<\/li>\n
    4. The findTreeDiameter function creates a graph using the given edges and finds the diameter of the tree through two BFS calls.<\/li>\n<\/ol>\n
      Execution Result<\/h2>\n
      When the code is executed, it produces the following output:<\/p>\n
      Diameter of the tree: 3<\/pre>\n
      This indicates the longest path between node 4 and node 5.<\/p>\n
      Conclusion<\/h2>\n
      In this lesson, we dealt with the problem of finding the diameter of a tree. This problem can be solved using DFS or BFS and helps enhance understanding of tree structures. It is a question that often appears in actual coding tests, so be sure to practice enough to become familiar with algorithm implementation. It is also beneficial to experiment with various tree cases for a deeper understanding.<\/p>\n
      In the next lesson, we will cover more algorithm problems, so please stay tuned!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      Solving various algorithm problems for coding test preparation is very helpful in improving your programming skills. This time, we will take a deep dive into the ‘Finding the Diameter of a Tree’ problem. Understanding and knowing how to solve tree structures is very useful, as they frequently appear in many programming problems. Problem Description A … \ub354 \ubcf4\uae30 “Swift Coding Test Course, Finding the Diameter of a Tree”<\/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-34902","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"\nSwift Coding Test Course, Finding the Diameter of a Tree - \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\/34902\/\" \/>\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, Finding the Diameter of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Solving various algorithm problems for coding test preparation is very helpful in improving your programming skills. This time, we will take a deep dive into the ‘Finding the Diameter of a Tree’ problem. Understanding and knowing how to solve tree structures is very useful, as they frequently appear in many programming problems. Problem Description A … \ub354 \ubcf4\uae30 "Swift Coding Test Course, Finding the Diameter of a Tree"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34902\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:33:23+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:02+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\/34902\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34902\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Finding the Diameter of a Tree\",\"datePublished\":\"2024-11-01T09:33:23+00:00\",\"dateModified\":\"2024-11-01T11:26:02+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34902\/\"},\"wordCount\":406,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34902\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34902\/\",\"name\":\"Swift Coding Test Course, Finding the Diameter of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:33:23+00:00\",\"dateModified\":\"2024-11-01T11:26:02+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34902\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34902\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34902\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Finding the Diameter of a Tree\"}]},{\"@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, Finding the Diameter of a Tree - \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\/34902\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Finding the Diameter of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Solving various algorithm problems for coding test preparation is very helpful in improving your programming skills. This time, we will take a deep dive into the ‘Finding the Diameter of a Tree’ problem. Understanding and knowing how to solve tree structures is very useful, as they frequently appear in many programming problems. Problem Description A … \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Finding the Diameter of a Tree\"","og_url":"https:\/\/atmokpo.com\/w\/34902\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:33:23+00:00","article_modified_time":"2024-11-01T11:26:02+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\/34902\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34902\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Finding the Diameter of a Tree","datePublished":"2024-11-01T09:33:23+00:00","dateModified":"2024-11-01T11:26:02+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34902\/"},"wordCount":406,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34902\/","url":"https:\/\/atmokpo.com\/w\/34902\/","name":"Swift Coding Test Course, Finding the Diameter of a Tree - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:33:23+00:00","dateModified":"2024-11-01T11:26:02+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34902\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34902\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34902\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Finding the Diameter of a Tree"}]},{"@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\/34902","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=34902"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34902\/revisions"}],"predecessor-version":[{"id":34903,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34902\/revisions\/34903"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34902"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34902"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34902"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}