[백준] 전력난

[hye-on]

🔗 전력난

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; //02:39 ~ 3:13 //크루스칼 int n, m; priority_queue>,vector>>,greater>>>pq; vectorparent; int findParent(int a) { if (parent[a] == a) return a; return parent[a] = findParent(parent[a]); } void unionParent(int a,int b) { a = findParent(a); b = findParent(b); if (a < b) parent[b] = a; else parent[a] = b; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (true) { cin >> m >> n; //집의 수, 길의수 if (m == 0 && n == 0) { break; } parent.resize(m); for (int i = 0; i < m; i++) parent[i] = i; // 크루스칼을 위해 우선순위큐에 담아줌 int ans = 0; int x = 0, y = 0, z = 0; for (int i = 0; i < n; i++) { cin >> x >> y >> z; pq.push({ z,{x,y} }); ans += z; } //union-find로 최소비용으로 합집합 만들기 while (!pq.empty()) { int v = pq.top().first; int x = pq.top().second.first; int y = pq.top().second.second; pq.pop(); if (findParent(x) != findParent(y)) { unionParent(x, y); ans -= v; } } cout << ans << "\n"; } } ```

코멘트

- 왜 틀리지 했는데 여러케이스가 있다는 걸 간과했네요..
- 크루스칼 살짤 헷갈렸는데 오랫만에 풀어서 복습해서 좋았습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 14:17 start! 15:32 end! */ public class Main { /** * 최소 스패닝 트리? */ static int[] parent; public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new StringBuilder(); while(true) { st = new StringTokenizer(bf.readLine()); int m = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken()); if(m == 0 && n == 0) break; PriorityQueue pq = new PriorityQueue<>((a, b) -> a.dist - b.dist); int total = 0; for(int i = 0; i < n; ++i) { st = new StringTokenizer(bf.readLine()); int h1 = Integer.parseInt(st.nextToken()); int h2 = Integer.parseInt(st.nextToken()); int dist = Integer.parseInt(st.nextToken()); total += dist; pq.offer(new Edge(h1, h2, dist)); } parent = new int[m]; for(int i = 0; i < m; ++i) parent[i] = i; int cost = 0; while(!pq.isEmpty()) { Edge edge = pq.poll(); if(find(edge.h1) == find(edge.h2)) continue; if(edge.h1 >= edge.h2) union(edge.h1, edge.h2); else union(edge.h2, edge.h1); cost += edge.dist; } sb.append(total - cost).append("\n"); } System.out.println(sb.toString()); } public static class Edge { int h1; int h2; int dist; public Edge(int h1, int h2, int dist) { this.h1 = h1; this.h2 = h2; this.dist = dist; } } public static void union(int h1, int h2) { int p1 = find(h1); int p2 = find(h2); if(p1 != p2) { parent[p2] = p1; } } public static int find(int h) { if(parent[h] == h) return h; return parent[h] = find(parent[h]); // ❗️ 이 부분 때문에 시간 초과가 났었음! } } ```

코멘트

- 최소 스패닝 트리 문제인건 알아보기 쉬웠는데, 입력값이 여러번 나올 수 있다는 걸 놓쳐서 시간을 썼네요ㅜㅜ
- find() 메서드에서 최적화를 하지 않으면 시간 초과가 나는데.. 알고리즘은 맞는데 요론거 때문에 틀리면 마음이 좀 아프네요..