Java Coding Test Course, Breadth-First Search - \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\/33335\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems. 1. Overview of Breadth-First Search (BFS) Breadth-First Search is an algorithm used to explore … \ub354 \ubcf4\uae30 "Java Coding Test Course, Breadth-First Search"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33335\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:15:39+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:39:07+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=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Breadth-First Search\",\"datePublished\":\"2024-11-01T09:15:39+00:00\",\"dateModified\":\"2024-11-01T11:39:07+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\"},\"wordCount\":566,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33335\/\",\"name\":\"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:15:39+00:00\",\"dateModified\":\"2024-11-01T11:39:07+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33335\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java Coding Test Course, Breadth-First Search\"}]},{\"@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_head_json":{"title":"Java Coding Test Course, Breadth-First Search - \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\/33335\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems. 1. Overview of Breadth-First Search (BFS) Breadth-First Search is an algorithm used to explore … \ub354 \ubcf4\uae30 \"Java Coding Test Course, Breadth-First Search\"","og_url":"https:\/\/atmokpo.com\/w\/33335\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:15:39+00:00","article_modified_time":"2024-11-01T11:39:07+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":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33335\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33335\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Breadth-First Search","datePublished":"2024-11-01T09:15:39+00:00","dateModified":"2024-11-01T11:39:07+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33335\/"},"wordCount":566,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33335\/","url":"https:\/\/atmokpo.com\/w\/33335\/","name":"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:15:39+00:00","dateModified":"2024-11-01T11:39:07+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33335\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java Coding Test Course, Breadth-First Search"}]},{"@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\/33335","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=33335"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33335\/revisions"}],"predecessor-version":[{"id":33336,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33335\/revisions\/33336"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":33335,"date":"2024-11-01T09:15:39","date_gmt":"2024-11-01T09:15:39","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33335"},"modified":"2024-11-01T11:39:07","modified_gmt":"2024-11-01T11:39:07","slug":"java-coding-test-course-breadth-first-search","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33335\/","title":{"rendered":"Java Coding Test Course, Breadth-First Search"},"content":{"rendered":"

<\/p>\n

Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems.<\/p>\n

1. Overview of Breadth-First Search (BFS)<\/h2>\n
Breadth-First Search is an algorithm used to explore graph or tree structures, starting from the root node and visiting adjacent nodes in priority order. It is primarily implemented using a queue data structure. BFS is useful for finding the shortest path to a specific node and is suitable for problems involving shortest distances.<\/p>\n

1.1 Characteristics of BFS<\/h3>\n

Searches all nodes at the same depth<\/li>\n
Guarantees the shortest path<\/li>\n

May use a lot of memory<\/li>\n<\/ul>\n

1.2 Time Complexity of BFS<\/h3>\n
The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges. This is because each node and edge is visited once.<\/p>\n

2. Example Problem<\/h2>\n

Problem Description<\/h3>\n
This problem involves calculating the shortest distances from a starting node in a given graph. The graph is provided in the form of an adjacency list, and you are required to write a function that returns the shortest distance to all nodes reachable from the starting node.<\/p>\n

Input<\/h4>\n

n (1 \u2264 n \u2264 1000): Number of nodes in the graph<\/li>\n
edges: An array of edge lists, where each edge is of the form [a, b]<\/li>\n

start: The starting node (an integer from 1 to n)<\/li>\n<\/ul>\n

Output<\/h4>\n
Returns an array containing the shortest distances from the starting node to each node. If a node is unreachable, denote it by -1.<\/p>\n

2.1 Example<\/h3>\n

\n    Input: \n    n = 5\n    edges = [[1, 2], [1, 3], [2, 4], [3, 5]]\n    start = 1\n\n    Output: \n    [0, 1, 1, 2, -1]\n    <\/pre>\n3. Problem Solving Process<\/h2>\nTo solve this problem, we will proceed through the following steps.<\/p>\n
3.1 Convert Input Data to Graph Form<\/h3>\nFirst, we will convert the edge list into an adjacency list representation of the graph. This allows us to easily find adjacent nodes for each node.<\/p>\n
3.2 Implement BFS Algorithm<\/h3>\nWe will perform BFS starting from the starting node using a queue. The current node is added to the queue, allowing us to explore adjacent nodes. We will record the shortest distance for visited nodes in an array for later use.<\/p>\n
3.2.1 Progress of BFS Exploration<\/h4>\n\nAdd the starting node to the queue and set the initial value (0) in the distance array.<\/li>\n
Poll a node from the queue and check all adjacent nodes to that node.<\/li>\n
If an adjacent node has not been visited, update the distance and add it to the queue.<\/li>\n
Repeat this process until all nodes have been visited.<\/li>\n<\/ol>\n3.3 Generate Final Results<\/h3>\nAfter exploring all nodes, we return the distance array to display the shortest paths. Nodes that are unreachable are indicated by -1.<\/p>\n
4. Java Code Example<\/h2>\n\nimport java.util.*;\n\npublic class BFSDistance {\n    public static int[] bfsDistance(int n, int[][] edges, int start) {\n        List> graph = new ArrayList<>();\n        for (int i = 0; i <= n; i++) {\n            graph.add(new ArrayList<>());\n        }\n        \n        \/\/ Create the graph adjacency list\n        for (int[] edge : edges) {\n            graph.get(edge[0]).add(edge[1]);\n            graph.get(edge[1]).add(edge[0]); \/\/ Undirected graph\n        }\n\n        int[] distances = new int[n + 1];\n        Arrays.fill(distances, -1); \/\/ Set initial distance to -1\n        distances[start] = 0; \/\/ Distance to the starting point is 0\n        \n        Queue queue = new LinkedList<>();\n        queue.add(start);\n        \n        while (!queue.isEmpty()) {\n            int currentNode = queue.poll();\n            for (int neighbor : graph.get(currentNode)) {\n                if (distances[neighbor] == -1) { \/\/ If not visited\n                    distances[neighbor] = distances[currentNode] + 1;\n                    queue.add(neighbor);\n                }\n            }\n        }\n        \n        return Arrays.copyOfRange(distances, 1, distances.length); \/\/ Return from 1 to n\n    }\n\n    public static void main(String[] args) {\n        int n = 5;\n        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 5}};\n        int start = 1;\n\n        int[] result = bfsDistance(n, edges, start);\n        System.out.println(Arrays.toString(result)); \/\/ [0, 1, 1, 2, -1]\n    }\n}\n<\/code><\/pre>\n5. Conclusion<\/h2>\nIn this lecture, we demonstrated the concept and application of Breadth-First Search (BFS). BFS is a highly effective algorithm for finding the shortest path and a powerful tool for exploring graphs and trees. We encourage you to practice and apply this technique in coding tests. In the next lecture, we will cover Depth-First Search (DFS)!<\/p>\n
6. Additional Practice Problems<\/h2>\nWe provide additional problems for practicing Breadth-First Search. Try solving the problems below.<\/p>\n
Problem: Finding Shortest Path<\/h3>\nGiven an unweighted graph, determine the shortest paths from the starting node to all other nodes. Additionally, learn how to use Dijkstra’s algorithm to find the shortest path in weighted graphs.<\/p>\n
Reference Materials<\/h3>\n\nBFS – Wikipedia<\/a><\/li>\n
BFS Implementation – GeeksforGeeks<\/a><\/li>\n<\/ul>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems. 1. Overview of Breadth-First Search (BFS) Breadth-First Search is an algorithm used to explore … \ub354 \ubcf4\uae30 “Java Coding Test Course, Breadth-First Search”<\/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":[139],"tags":[],"class_list":["post-33335","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"\nJava Coding Test Course, Breadth-First Search - \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\/33335\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems. 1. Overview of Breadth-First Search (BFS) Breadth-First Search is an algorithm used to explore … \ub354 \ubcf4\uae30 "Java Coding Test Course, Breadth-First Search"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33335\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:15:39+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:39:07+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=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Breadth-First Search\",\"datePublished\":\"2024-11-01T09:15:39+00:00\",\"dateModified\":\"2024-11-01T11:39:07+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\"},\"wordCount\":566,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33335\/\",\"name\":\"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:15:39+00:00\",\"dateModified\":\"2024-11-01T11:39:07+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33335\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java Coding Test Course, Breadth-First Search\"}]},{\"@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":"Java Coding Test Course, Breadth-First Search - \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\/33335\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Understanding various algorithms and data structures is important in coding tests. One of them is Breadth-First Search (BFS). In this article, we will explain the basic concepts of BFS, provide example problems, and outline a step-by-step approach to solving those problems. 1. Overview of Breadth-First Search (BFS) Breadth-First Search is an algorithm used to explore … \ub354 \ubcf4\uae30 \"Java Coding Test Course, Breadth-First Search\"","og_url":"https:\/\/atmokpo.com\/w\/33335\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:15:39+00:00","article_modified_time":"2024-11-01T11:39:07+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":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33335\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33335\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Breadth-First Search","datePublished":"2024-11-01T09:15:39+00:00","dateModified":"2024-11-01T11:39:07+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33335\/"},"wordCount":566,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33335\/","url":"https:\/\/atmokpo.com\/w\/33335\/","name":"Java Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:15:39+00:00","dateModified":"2024-11-01T11:39:07+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33335\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33335\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java Coding Test Course, Breadth-First Search"}]},{"@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\/33335","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=33335"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33335\/revisions"}],"predecessor-version":[{"id":33336,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33335\/revisions\/33336"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

1.2 Time Complexity of BFS<\/h3>\n
The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges. This is because each node and edge is visited once.<\/p>\n

2. Example Problem<\/h2>\n

Output<\/h4>\n
Returns an array containing the shortest distances from the starting node to each node. If a node is unreachable, denote it by -1.<\/p>\n

3. Problem Solving Process<\/h2>\n
To solve this problem, we will proceed through the following steps.<\/p>\n

3.1 Convert Input Data to Graph Form<\/h3>\n
First, we will convert the edge list into an adjacency list representation of the graph. This allows us to easily find adjacent nodes for each node.<\/p>\n

3.2 Implement BFS Algorithm<\/h3>\n
We will perform BFS starting from the starting node using a queue. The current node is added to the queue, allowing us to explore adjacent nodes. We will record the shortest distance for visited nodes in an array for later use.<\/p>\n

3.3 Generate Final Results<\/h3>\n
After exploring all nodes, we return the distance array to display the shortest paths. Nodes that are unreachable are indicated by -1.<\/p>\n

6. Additional Practice Problems<\/h2>\n
We provide additional problems for practicing Breadth-First Search. Try solving the problems below.<\/p>\n

Problem: Finding Shortest Path<\/h3>\n
Given an unweighted graph, determine the shortest paths from the starting node to all other nodes. Additionally, learn how to use Dijkstra’s algorithm to find the shortest path in weighted graphs.<\/p>\n

1.2 Time Complexity of BFS<\/h3>\nThe time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges. This is because each node and edge is visited once.<\/p>\n

2. Example Problem<\/h2>\n

Output<\/h4>\nReturns an array containing the shortest distances from the starting node to each node. If a node is unreachable, denote it by -1.<\/p>\n

3. Problem Solving Process<\/h2>\nTo solve this problem, we will proceed through the following steps.<\/p>\n

3.1 Convert Input Data to Graph Form<\/h3>\nFirst, we will convert the edge list into an adjacency list representation of the graph. This allows us to easily find adjacent nodes for each node.<\/p>\n

3.2 Implement BFS Algorithm<\/h3>\nWe will perform BFS starting from the starting node using a queue. The current node is added to the queue, allowing us to explore adjacent nodes. We will record the shortest distance for visited nodes in an array for later use.<\/p>\n

3.3 Generate Final Results<\/h3>\nAfter exploring all nodes, we return the distance array to display the shortest paths. Nodes that are unreachable are indicated by -1.<\/p>\n

6. Additional Practice Problems<\/h2>\nWe provide additional problems for practicing Breadth-First Search. Try solving the problems below.<\/p>\n

Problem: Finding Shortest Path<\/h3>\nGiven an unweighted graph, determine the shortest paths from the starting node to all other nodes. Additionally, learn how to use Dijkstra’s algorithm to find the shortest path in weighted graphs.<\/p>\n

1.2 Time Complexity of BFS<\/h3>\n
The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges. This is because each node and edge is visited once.<\/p>\n

Output<\/h4>\n
Returns an array containing the shortest distances from the starting node to each node. If a node is unreachable, denote it by -1.<\/p>\n

3. Problem Solving Process<\/h2>\n
To solve this problem, we will proceed through the following steps.<\/p>\n

3.1 Convert Input Data to Graph Form<\/h3>\n
First, we will convert the edge list into an adjacency list representation of the graph. This allows us to easily find adjacent nodes for each node.<\/p>\n

3.2 Implement BFS Algorithm<\/h3>\n
We will perform BFS starting from the starting node using a queue. The current node is added to the queue, allowing us to explore adjacent nodes. We will record the shortest distance for visited nodes in an array for later use.<\/p>\n

3.3 Generate Final Results<\/h3>\n
After exploring all nodes, we return the distance array to display the shortest paths. Nodes that are unreachable are indicated by -1.<\/p>\n

6. Additional Practice Problems<\/h2>\n
We provide additional problems for practicing Breadth-First Search. Try solving the problems below.<\/p>\n

Problem: Finding Shortest Path<\/h3>\n
Given an unweighted graph, determine the shortest paths from the starting node to all other nodes. Additionally, learn how to use Dijkstra’s algorithm to find the shortest path in weighted graphs.<\/p>\n