{"id":33498,"date":"2024-11-01T09:17:09","date_gmt":"2024-11-01T09:17:09","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33498"},"modified":"2024-11-01T11:38:17","modified_gmt":"2024-11-01T11:38:17","slug":"java-coding-test-course-finding-minimum-cost","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33498\/","title":{"rendered":"Java Coding Test Course, Finding Minimum Cost"},"content":{"rendered":"<div class=\"post\">\n<p>To prepare for coding tests, it is important to solve various algorithm problems. In this lecture, we will cover the problem of &#8216;Finding the Minimum Cost&#8217;. This problem requires graph theory and dynamic programming techniques. It will further enhance your programming skills.<\/p>\n<h2>Problem Description<\/h2>\n<p>In the given directed graph, there are several nodes and edges. Each edge has a specific cost. We need to find the minimum cost to move from one node to another. There may be multiple nodes, and there may be several paths between any two nodes.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>The first line contains the number of nodes N and the number of edges M (1 \u2264 N \u2264 100, 1 \u2264 M \u2264 1000)<\/li>\n<li>The next M lines contain edge information. Each edge is given in the format <code>u v c<\/code>, which means the cost of the edge from node u to v is c. (1 \u2264 c \u2264 1000)<\/li>\n<li>The last line contains the starting node S and the target node T.<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>Print the minimum cost to go from the starting node S to the target node T. If it is not reachable, print -1.<\/p>\n<h2>Example Problem<\/h2>\n<pre>\n    <code>\n    Input:\n    5 6\n    1 2 2\n    1 3 3\n    2 3 1\n    2 4 4\n    3 4 1\n    4 5 1\n    1 5\n    \n    Output:\n    6\n    <\/code>\n    <\/pre>\n<h2>Algorithm Idea<\/h2>\n<p>This problem is similar to finding the shortest path in a graph. We can efficiently solve the problem using Dijkstra&#8217;s algorithm. This algorithm is optimized for finding the shortest path from one node to another. We will use this algorithm to track the minimum cost from the starting node to the target node.<\/p>\n<h2>Description of Dijkstra&#8217;s Algorithm<\/h2>\n<p>Dijkstra&#8217;s algorithm works as follows:<\/p>\n<ol>\n<li>First, initialize the distance from the starting node to each node to infinity, except for the starting node which should be initialized to 0.<\/li>\n<li>Use a priority queue to select the node that can be accessed with the current minimum cost.<\/li>\n<li>Update the costs for adjacent nodes of the chosen node. If a new path has a better cost, update that node and add it to the queue.<\/li>\n<li>Repeat this process until the target node is reached. After processing all nodes, return the final distance to the target node.<\/li>\n<\/ol>\n<h2>Java Code Implementation<\/h2>\n<pre>\n    <code>\n    import java.util.*;\n\n    public class MinCostPath {\n        static class Edge {\n            int to, cost;\n\n            Edge(int to, int cost) {\n                this.to = to;\n                this.cost = cost;\n            }\n        }\n\n        public static void main(String[] args) {\n            Scanner sc = new Scanner(System.in);\n        \n            int N = sc.nextInt(); \/\/ Number of nodes\n            int M = sc.nextInt(); \/\/ Number of edges\n            \n            List<List<Edge>> graph = new ArrayList<>();\n            for (int i = 0; i <= N; i++) {\n                graph.add(new ArrayList<>());\n            }\n        \n            for (int i = 0; i < M; i++) {\n                int u = sc.nextInt();\n                int v = sc.nextInt();\n                int c = sc.nextInt();\n                graph.get(u).add(new Edge(v, c));\n            }\n            \n            int S = sc.nextInt(); \/\/ Starting node\n            int T = sc.nextInt(); \/\/ Target node\n            \n            System.out.println(dijkstra(N, graph, S, T));\n        }\n        \n        static int dijkstra(int n, List<List<Edge>> graph, int start, int target) {\n            int[] dist = new int[n + 1];\n            Arrays.fill(dist, Integer.MAX_VALUE);\n            dist[start] = 0;\n        \n            PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.cost));\n            pq.add(new Edge(start, 0));\n        \n            while (!pq.isEmpty()) {\n                Edge current = pq.poll();\n        \n                if (current.to == target) {\n                    return dist[target];\n                }\n        \n                for (Edge edge : graph.get(current.to)) {\n                    if (dist[current.to] + edge.cost < dist[edge.to]) {\n                        dist[edge.to] = dist[current.to] + edge.cost;\n                        pq.add(new Edge(edge.to, dist[edge.to]));\n                    }\n                }\n            }\n        \n            return -1; \/\/ If not reachable\n        }\n    }\n    <\/code>\n    <\/pre>\n<h2>Code Explanation<\/h2>\n<p>In the above code:<\/p>\n<ul>\n<li>First, we get the number of nodes (N) and edges (M) as input.<\/li>\n<li>We input the information for each edge and store the graph in the form of an adjacency list.<\/li>\n<li>We perform initialization tasks for Dijkstra's algorithm. We create a distance array (dist) and set the distance of the starting node to 0.<\/li>\n<li>Using a priority queue, we iteratively update the shortest paths for the adjacent nodes of the current node.<\/li>\n<li>When we reach the target node, we return that distance, and if it is not reachable, we return -1.<\/li>\n<\/ul>\n<h2>Optimizations and Precautions<\/h2>\n<p>Dijkstra's algorithm is valid when all edge weights are non-negative. If there are negative edges, we should consider using the Bellman-Ford algorithm. Additionally, when optimizing performance using a priority queue, it is advisable to use a min-heap.<\/p>\n<h2>Conclusion<\/h2>\n<p>In this lecture, we learned the Dijkstra's algorithm through the 'Finding the Minimum Cost' problem. By practicing solving algorithm problems, we hope you gain confidence in coding tests and further improve your problem-solving skills. In the next session, we will introduce more diverse algorithms.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>To prepare for coding tests, it is important to solve various algorithm problems. In this lecture, we will cover the problem of &#8216;Finding the Minimum Cost&#8217;. This problem requires graph theory and dynamic programming techniques. It will further enhance your programming skills. Problem Description In the given directed graph, there are several nodes and edges. &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33498\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Java Coding Test Course, Finding Minimum Cost&#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":[139],"tags":[],"class_list":["post-33498","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Java Coding Test Course, Finding Minimum Cost - \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\/33498\/\" \/>\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, Finding Minimum Cost - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"To prepare for coding tests, it is important to solve various algorithm problems. In this lecture, we will cover the problem of &#8216;Finding the Minimum Cost&#8217;. This problem requires graph theory and dynamic programming techniques. It will further enhance your programming skills. Problem Description In the given directed graph, there are several nodes and edges. &hellip; \ub354 \ubcf4\uae30 &quot;Java Coding Test Course, Finding Minimum Cost&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33498\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:17:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:38:17+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\/33498\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33498\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Finding Minimum Cost\",\"datePublished\":\"2024-11-01T09:17:09+00:00\",\"dateModified\":\"2024-11-01T11:38:17+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33498\/\"},\"wordCount\":525,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33498\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33498\/\",\"name\":\"Java Coding Test Course, Finding Minimum Cost - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:17:09+00:00\",\"dateModified\":\"2024-11-01T11:38:17+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33498\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33498\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33498\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java Coding Test Course, Finding Minimum Cost\"}]},{\"@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, Finding Minimum Cost - \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\/33498\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Finding Minimum Cost - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"To prepare for coding tests, it is important to solve various algorithm problems. In this lecture, we will cover the problem of &#8216;Finding the Minimum Cost&#8217;. This problem requires graph theory and dynamic programming techniques. It will further enhance your programming skills. Problem Description In the given directed graph, there are several nodes and edges. &hellip; \ub354 \ubcf4\uae30 \"Java Coding Test Course, Finding Minimum Cost\"","og_url":"https:\/\/atmokpo.com\/w\/33498\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:17:09+00:00","article_modified_time":"2024-11-01T11:38:17+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\/33498\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33498\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Finding Minimum Cost","datePublished":"2024-11-01T09:17:09+00:00","dateModified":"2024-11-01T11:38:17+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33498\/"},"wordCount":525,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33498\/","url":"https:\/\/atmokpo.com\/w\/33498\/","name":"Java Coding Test Course, Finding Minimum Cost - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:17:09+00:00","dateModified":"2024-11-01T11:38:17+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33498\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33498\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33498\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java Coding Test Course, Finding Minimum Cost"}]},{"@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\/33498","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=33498"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33498\/revisions"}],"predecessor-version":[{"id":33499,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33498\/revisions\/33499"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}