{"id":34568,"date":"2024-11-01T09:29:31","date_gmt":"2024-11-01T09:29:31","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34568"},"modified":"2024-11-01T11:40:41","modified_gmt":"2024-11-01T11:40:41","slug":"javascript-coding-test-course-find-cities-at-a-specific-distance","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34568\/","title":{"rendered":"JavaScript Coding Test Course, Find Cities at a Specific Distance"},"content":{"rendered":"<div class=\"post\">\n<p>Hello, everyone! Today we will discuss an algorithm problem to find cities at a specific distance using JavaScript. This problem is one of the frequently featured topics in coding tests, where you will learn how to apply graph traversal and BFS (Breadth-First Search) techniques.<\/p>\n<h2>Problem Description<\/h2>\n<p>Write a function that returns a list of cities located at a specific distance starting from the given two vertices. The cities are connected by edges, and it is assumed that the distance calculation for each edge is equal to 1.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>n: the number of cities (1 \u2264 n \u2264 300,000)<\/li>\n<li>edges: the edges connecting each city, given as a 2D array. edges[i] = [a, b] means city a is directly connected to city b.<\/li>\n<li>start: the city from which the distance calculation will start (1 \u2264 start \u2264 n)<\/li>\n<li>distance: a specific distance k (0 \u2264 distance \u2264 n)<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>Return an array of cities that are at a specific distance, sorted in ascending order. If there are no such cities, return an empty array.<\/p>\n<h2>Problem Solving Strategy<\/h2>\n<p>The key to this problem is exploring the graph using the BFS algorithm. BFS is a technique that can explore all vertices in a graph and is suitable for finding the shortest path.<\/p>\n<p>The basic steps to solve the problem are as follows:<\/p>\n<ol>\n<li>Define the graph structure using the given edges array.<\/li>\n<li>Calculate the distance from the given start city to each city using BFS.<\/li>\n<li>Collect the cities whose distance matches the specific distance.<\/li>\n<li>Sort the resulting city list in ascending order and return it.<\/li>\n<\/ol>\n<h2>Implementation Steps<\/h2>\n<h3>Step 1: Graph Structuring<\/h3>\n<p>We will use an adjacency list to hold the connection information between cities. This will be composed of an object where each city is the key and the list of connected cities is the value.<\/p>\n<h3>Step 2: Implementing BFS Algorithm<\/h3>\n<p>Using BFS, we will calculate the distance from the starting city to each city and find the cities that can be reached at a specific distance.<\/p>\n<h3>Step 3: Processing and Returning Results<\/h3>\n<p>Collect the cities that match the specific distance, sort them, and return the result.<\/p>\n<h2>JavaScript Code Implementation<\/h2>\n<pre><code>\nfunction findCitiesAtDistance(n, edges, start, distance) {\n    \/\/ Step 1: Create the graph\n    const graph = Array.from({ length: n + 1 }, () =&gt; []);\n    for (const [a, b] of edges) {\n        graph[a].push(b);\n        graph[b].push(a); \/\/ Add to both sides for a bidirectional graph\n    }\n    \n    \/\/ Step 2: Set variables for BFS\n    const queue = [];\n    const distances = Array(n + 1).fill(-1); \/\/ Initialize distances\n    distances[start] = 0;\n    queue.push(start);\n    \n    \/\/ Perform BFS traversal\n    while (queue.length &gt; 0) {\n        const currentCity = queue.shift();\n        \n        for (const neighbor of graph[currentCity]) {\n            \/\/ If the city has not been visited\n            if (distances[neighbor] === -1) {\n                distances[neighbor] = distances[currentCity] + 1;\n                queue.push(neighbor);\n            }\n        }\n    }\n    \n    \/\/ Step 3: Find cities at a specific distance\n    const result = [];\n    for (let city = 1; city &lt;= n; city++) {\n        if (distances[city] === distance) {\n            result.push(city);\n        }\n    }\n\n    \/\/ Sort in ascending order\n    result.sort((a, b) =&gt; a - b);\n    return result;\n}\n    <\/code><\/pre>\n<h2>Code Explanation<\/h2>\n<p>The code above is a function that finds cities at a specific distance according to the given requirements. I will explain each step:<\/p>\n<h3>Graph Creation<\/h3>\n<p>We create the graph structure by iterating through the edges array and storing the connection information between each city. An adjacency list is used to keep the list of cities connected to each city.<\/p>\n<h3>BFS Implementation<\/h3>\n<p>This is the process of calculating distance values using BFS from the starting city. We use a distances array to record the distances of each city, marking visited cities as -1 to prevent duplication.<\/p>\n<h3>Result Processing<\/h3>\n<p>After exploring all the cities, we add the cities that match the specific distance to the result list and finally sort them in ascending order before returning.<\/p>\n<h2>Test Cases<\/h2>\n<p>Now let&#8217;s check the operation of the implemented code through some test cases.<\/p>\n<pre><code>\nconsole.log(findCitiesAtDistance(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4]], 5, 2)); \n\/\/ Output: [4, 5, 6]\nconsole.log(findCitiesAtDistance(4, [[1, 2], [1, 3], [2, 4]], 1, 2)); \n\/\/ Output: [4]\nconsole.log(findCitiesAtDistance(5, [[1, 2], [1, 3], [1, 4], [2, 5]], 1, 1)); \n\/\/ Output: [2, 3, 4]\nconsole.log(findCitiesAtDistance(7, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]], 1, 3)); \n\/\/ Output: [4]\nconsole.log(findCitiesAtDistance(3, [], 1, 1)); \n\/\/ Output: []\n    <\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>In this post, we covered an algorithm problem to find cities at a specific distance and explained the basic principles of graph traversal using BFS. Through this problem, we learned various concepts such as graph structuring, BFS implementation, and result processing. Since such problems are frequently presented in coding tests, understanding and practicing them is important. Next time, we will tackle more complex graph problems. Thank you!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello, everyone! Today we will discuss an algorithm problem to find cities at a specific distance using JavaScript. This problem is one of the frequently featured topics in coding tests, where you will learn how to apply graph traversal and BFS (Breadth-First Search) techniques. Problem Description Write a function that returns a list of cities &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34568\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;JavaScript Coding Test Course, Find Cities at a Specific Distance&#8221;<\/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":[141],"tags":[],"class_list":["post-34568","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>JavaScript Coding Test Course, Find Cities at a Specific Distance - \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\/34568\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Find Cities at a Specific Distance - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, everyone! Today we will discuss an algorithm problem to find cities at a specific distance using JavaScript. This problem is one of the frequently featured topics in coding tests, where you will learn how to apply graph traversal and BFS (Breadth-First Search) techniques. Problem Description Write a function that returns a list of cities &hellip; \ub354 \ubcf4\uae30 &quot;JavaScript Coding Test Course, Find Cities at a Specific Distance&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34568\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:29:31+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:40:41+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\/34568\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34568\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Find Cities at a Specific Distance\",\"datePublished\":\"2024-11-01T09:29:31+00:00\",\"dateModified\":\"2024-11-01T11:40:41+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34568\/\"},\"wordCount\":562,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34568\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34568\/\",\"name\":\"JavaScript Coding Test Course, Find Cities at a Specific Distance - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:29:31+00:00\",\"dateModified\":\"2024-11-01T11:40:41+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34568\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34568\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34568\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Find Cities at a Specific Distance\"}]},{\"@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":"JavaScript Coding Test Course, Find Cities at a Specific Distance - \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\/34568\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Find Cities at a Specific Distance - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, everyone! Today we will discuss an algorithm problem to find cities at a specific distance using JavaScript. This problem is one of the frequently featured topics in coding tests, where you will learn how to apply graph traversal and BFS (Breadth-First Search) techniques. Problem Description Write a function that returns a list of cities &hellip; \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Find Cities at a Specific Distance\"","og_url":"https:\/\/atmokpo.com\/w\/34568\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:29:31+00:00","article_modified_time":"2024-11-01T11:40:41+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\/34568\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34568\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Find Cities at a Specific Distance","datePublished":"2024-11-01T09:29:31+00:00","dateModified":"2024-11-01T11:40:41+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34568\/"},"wordCount":562,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34568\/","url":"https:\/\/atmokpo.com\/w\/34568\/","name":"JavaScript Coding Test Course, Find Cities at a Specific Distance - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:29:31+00:00","dateModified":"2024-11-01T11:40:41+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34568\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34568\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34568\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Find Cities at a Specific Distance"}]},{"@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\/34568","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=34568"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34568\/revisions"}],"predecessor-version":[{"id":34569,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34568\/revisions\/34569"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}