{"id":34132,"date":"2024-11-01T09:24:34","date_gmt":"2024-11-01T09:24:34","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34132"},"modified":"2024-11-01T10:58:29","modified_gmt":"2024-11-01T10:58:29","slug":"c-coding-test-course-pathfinding-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34132\/","title":{"rendered":"C++ Coding Test Course, Pathfinding"},"content":{"rendered":"

<\/p>\n

\n In this course, we will implement an algorithm to find paths in graphs using C++.
\n In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search).
\n During this process, we will solve problems that frequently appear in actual coding tests, and
\n we will explain the algorithm theory and implementation in detail.\n <\/p>\n

Problem Description<\/h2>\n

\n You need to solve the problem of finding the shortest path between two points in a given graph.
\n The graph consists of nodes and edges, with each node being connected to others.
\n This problem is generally provided in the following format:\n <\/p>\n

\n    Input:\n    6 7\n    0 1\n    0 2\n    1 3\n    1 4\n    2 5\n    4 5\n    3 5\n    0 5\n\n    Output:\n    2\n    <\/pre>\n
\n        The first line indicates the number of nodes (vertices) and the number of edges,
\n        while the subsequent lines represent the connection information for each edge.
\n        The last line signifies the start and end nodes.\n    <\/p>\n
Algorithm Theory<\/h2>\n
\n        Pathfinding in graphs can be performed using two methods: DFS (Depth-First Search) and BFS (Breadth-First Search).
\n        In this course, we will focus on finding the shortest path using BFS.
\n        BFS operates intuitively, proceeding by exploring all adjacent nodes using a queue.\n    <\/p>\n
Principle of BFS<\/h3>\n
\n        The basic operating principle of BFS is as follows:\n    <\/p>\n
    \n
  1. Add the starting node to the queue and mark it as visited.<\/li>\n
  2. Dequeue a node and explore all its adjacent nodes.<\/li>\n
  3. Add any unvisited adjacent nodes to the queue and mark them as visited.<\/li>\n
  4. Repeat steps 2 and 3 until the queue is empty.<\/li>\n<\/ol>\n
    \n        The reason BFS guarantees the shortest path is that it processes all nodes at the same level.
    \n        By searching based on levels, the shortest path is ensured.\n    <\/p>\n
    Problem-Solving Process<\/h2>\n
    \n        Now we will implement the algorithm necessary to solve the problem.
    \n        Below is a C++ code example for problem-solving.\n    <\/p>\n
    \n#include <iostream>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nint bfs(vector>& graph, int start, int end) {\n    queue q;\n    vector visited(graph.size(), false);\n    vector distance(graph.size(), -1);\n    \n    q.push(start);\n    visited[start] = true;\n    distance[start] = 0;\n\n    while (!q.empty()) {\n        int node = q.front();\n        q.pop();\n        \n        for (int neighbor : graph[node]) {\n            if (!visited[neighbor]) {\n                visited[neighbor] = true;\n                distance[neighbor] = distance[node] + 1;\n                q.push(neighbor);\n                \n                if (neighbor == end) {\n                    return distance[neighbor];\n                }\n            }\n        }\n    }\n    return -1; \/\/ If there is no path \n}\n\nint main() {\n    int n, m;\n    cin >> n >> m;\n    vector> graph(n);\n    \n    for (int i = 0; i < m; i++) {\n        int u, v;\n        cin >> u >> v;\n        graph[u].push_back(v);\n        graph[v].push_back(u); \/\/ undirected graph\n    }\n\n    int start, end;\n    cin >> start >> end;\n\n    int result = bfs(graph, start, end);\n    cout << result << endl;\n\n    return 0;\n}\n    <\/vector<\/int><\/bool><\/int><\/vector<\/code><\/pre>\n
    Code Explanation<\/h3>\n
    \n        The code above takes the number of nodes and edges as input,
    \n        constructs the graph based on the edge information, and then uses BFS to
    \n        find the shortest path between the starting and ending nodes.\n    <\/p>\n
      \n
    1. First, we include the necessary header files and declare using namespace std;<\/code>.<\/li>\n
    2. The bfs<\/code> function takes the graph, starting node, and ending node as parameters.<\/li>\n
    3. A queue is declared, and a vector visited<\/code> to indicate visitation status is initialized.<\/li>\n
    4. The starting node is added to the queue and marked as visited.<\/li>\n
    5. The process continues while the queue is not empty, dequeuing nodes and exploring adjacent nodes.<\/li>\n
    6. Unvisited adjacent nodes are added to the queue and their distance information is updated.<\/li>\n
    7. When reaching the ending node, the corresponding distance is returned.<\/li>\n
    8. The distance information is initialized to -1<\/code>; when there is no path, it returns -1<\/code>.<\/li>\n<\/ol>\n
      Results and Analysis<\/h2>\n
      \n        Compiling the above code and executing it with the sample input will print
      \n        the shortest path between the starting node and the ending node.
      \n        Since BFS explores all adjacent nodes, it guarantees the shortest path.
      \n        As the size of the graph increases, the search time increases proportionally, but
      \n        BFS is a suitable algorithm for most graph problems.\n    <\/p>\n
      Complexity Analysis<\/h3>\n
      \n        The time complexity of BFS is O(V + E)<\/code>, where V<\/code> is the number of nodes,
      \n        and E<\/code> is the number of edges. The memory complexity is also O(V)<\/code>.
      \n        This complexity can vary depending on the structure of the graph.
      \n        In the worst case (e.g., complete graph), E<\/code> can become V^2<\/code>.\n    <\/p>\n
      Conclusion<\/h2>\n
      \n        In this course, we solved the problem of finding the shortest path in a graph using C++
      \n        through the BFS algorithm. Understanding and implementing BFS is
      \n        an important aspect of coding tests, so be sure to practice thoroughly.
      \n        I hope you can build your skills through a wider variety of problems in the future.\n    <\/p>\n
      <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
      In this course, we will implement an algorithm to find paths in graphs using C++. In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search). During this process, we will solve problems that frequently appear in actual coding tests, and we will explain the algorithm theory and implementation in … \ub354 \ubcf4\uae30 “C++ 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":[111],"tags":[],"class_list":["post-34132","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ 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\/34132\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this course, we will implement an algorithm to find paths in graphs using C++. In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search). During this process, we will solve problems that frequently appear in actual coding tests, and we will explain the algorithm theory and implementation in … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Pathfinding"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34132\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:24:34+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:29+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=\"1\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Pathfinding\",\"datePublished\":\"2024-11-01T09:24:34+00:00\",\"dateModified\":\"2024-11-01T10:58:29+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/\"},\"wordCount\":579,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34132\/\",\"name\":\"C++ Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:24:34+00:00\",\"dateModified\":\"2024-11-01T10:58:29+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34132\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34132\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ 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":"C++ 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\/34132\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this course, we will implement an algorithm to find paths in graphs using C++. In particular, we aim to cover how to find the shortest path using BFS (Breadth-First Search). During this process, we will solve problems that frequently appear in actual coding tests, and we will explain the algorithm theory and implementation in … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Pathfinding\"","og_url":"https:\/\/atmokpo.com\/w\/34132\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:24:34+00:00","article_modified_time":"2024-11-01T10:58:29+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":"1\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34132\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34132\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Pathfinding","datePublished":"2024-11-01T09:24:34+00:00","dateModified":"2024-11-01T10:58:29+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34132\/"},"wordCount":579,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34132\/","url":"https:\/\/atmokpo.com\/w\/34132\/","name":"C++ Coding Test Course, Pathfinding - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:24:34+00:00","dateModified":"2024-11-01T10:58:29+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34132\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34132\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34132\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ 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\/34132","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=34132"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34132\/revisions"}],"predecessor-version":[{"id":34133,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34132\/revisions\/34133"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34132"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34132"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}