{"id":33774,"date":"2024-11-01T09:20:13","date_gmt":"2024-11-01T09:20:13","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33774"},"modified":"2024-11-01T12:27:25","modified_gmt":"2024-11-01T12:27:25","slug":"%ed%8c%8c%ec%9d%b4%ec%8d%ac-%ec%bd%94%eb%94%a9-%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%ec%86%8c-%ec%8b%a0%ec%9e%a5-%ed%8a%b8%eb%a6%ac","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33774\/","title":{"rendered":"Python coding test course, minimum spanning tree"},"content":{"rendered":"

<\/p>\n

1. What is a Minimum Spanning Tree?<\/h2>\n

A Minimum Spanning Tree (MST) is a subgraph of a connected graph that includes all vertices while minimizing the sum of the weights of the edges. In other words, the Minimum Spanning Tree is the process of finding a tree that connects all vertices in the given graph with the least total cost while avoiding cycles.<\/p>\n

2. Problem Description<\/h2>\n

The following is the Minimum Spanning Tree problem:<\/p>\n

\n

Given n<\/code> cities and m<\/code> roads, find the minimum cost to connect all the cities with roads.<\/p>\n

Input format: The first line contains two integers n<\/code> (the number of cities) and m<\/code> (the number of roads). The next m<\/code> lines contain three integers a<\/code>, b<\/code>, c<\/code> representing that the cost of the road connecting city a<\/code> and city b<\/code> is c<\/code>.<\/p>\n<\/blockquote>\n

3. Approach<\/h2>\n

To solve the Minimum Spanning Tree problem, two algorithms are commonly used:<\/p>\n