[ Baekjoon - 10/11 ] - 1647번: 도시 분할 계획

• 문제 링크 : https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

• 소요 시간 : 1시간 반

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 256MB
   • 문제
     
     • N개의 집(2≤N≤100,000), M개의 길 수(1≤M≤1,000,000), 길 유지비(1≤C≤1,000)
     • 두개의 마을로 분할할때, 나머지 길의 유지비의 최솟값을 출력하는 문제
   • 이해
     • N개의 집(노드), M개의 길 수(간선), C의 유지비(가중치)이므로, 무방향 가중치 그래프 형식이고, 이를 두 마을로 분리하는게 목적이다.
     • 모든 노드를 탐색하며 최소의 가중치를 선택하는방식으로 가도되고,
       전체를 큰 집합으로 보고, 두개의 집합으로 분리하는 방식으로 가도된다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 예제로 어떤식으로 나뉘는지 시각적으로 해석하기 위해 그려봤지만.. 사실상 그림으로 보고 이건 바로 이렇게 나뉘어지겠다 같은 생각은 들지 않아서 그려본채로 오랜시간 관찰해본것같다
     < 사실상.. 최소 스패닝 트리 개념을 잊고있었음 ㅋㅋㅋㅋㅋㅋ 공부해야지..ㅠ>
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 인접리스트와 BFS를 이용한 MST[중에서도 Prim])
     • Prim알고리즘을 통해 모든 노드를 돌면서 가중치가 작은 간선들이 선택되도록 한 뒤,
       이때까지의 가중치의 합에서 가장 큰 가중치를 빼면 그게 최솟값이 된다! - Java11로 구현함
   • 2nd 접근 - union-find연산을 활용)
     • 이 방법도 크게 다르지 않은데, Prim을 Union-Find로도 구현이 가능하다는 점이다.
     • 정렬을 한 뒤, 합집합연산을 차례차례 하면서 가중치를 저장해뒀다가, 가장 큰 가중치를 제외한 나머지의 합을 출력하면 된다. - Python 3으로 구현함
4. 위 계획을 검증
   • 최적의 경로에서의 유지비(간선) 합에서 가장 비싼 유지비가 들어간 간선을 빼면 그게 최소 유지비가 된다.
   • 이에 따른 방법이었기때문에, 주로 잡은 구현체가 무엇이냐만 다를뿐 내부는 같다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.io.*;
         import java.util.*;
         
         public class Main {
             static int N,M;
             static List<Node>[] nodes;
             static boolean[] vis;
             static int cnt=0,weight_sum=0,max_weight=0;
         
             public static void main(String[] args) throws IOException {
                 //System.setIn(new FileInputStream("src/input.txt"));
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                 StringTokenizer st = new StringTokenizer(br.readLine());
         
                 N = Integer.parseInt(st.nextToken());
                 M = Integer.parseInt(st.nextToken());
         
                 nodes = new ArrayList[N+1];
                 for (int n = 1; n <= N; n++) {
                     nodes[n] = new ArrayList<>();
                 }
         
                 for(int m=0; m<M; m++){
                     st = new StringTokenizer(br.readLine());
                     int a = Integer.parseInt(st.nextToken());
                     int b = Integer.parseInt(st.nextToken());
                     int w = Integer.parseInt(st.nextToken());
         
                     nodes[a].add(new Node(b, w));
                     nodes[b].add(new Node(a, w));
                 }
         
                 vis = new boolean[N+1];
         
                 PriorityQueue<Node> q = new PriorityQueue<Node>();
                 q.add(new Node(1, 0));
         
                 while (true) {
                     Node cur = q.poll();
         
                     if (vis[cur.idx])
                         continue;
         
                     vis[cur.idx] = true;
                     weight_sum += cur.weight;
                     max_weight = Math.max(max_weight, cur.weight);
                     cnt++;
         
                     if (cnt == N)
                         break;
         
                     for (Node v : nodes[cur.idx]) {
                         if (!vis[v.idx]) {
                             q.add(new Node(v.idx, v.weight));
                         }
                     }
                 }
                 System.out.println(weight_sum-max_weight);
             }
         }
         class Node implements Comparable<Node>{
             int idx;
             int weight;
         
             public Node(int idx, int weight) {
                 this.idx = idx;
                 this.weight = weight;
             }
         
             @Override
             public int compareTo(Node e) {
                 return this.weight - e.weight;
             }
         }

   2. Python 3

      1. import sys
         input = sys.stdin.readline
         
         def find_parent(x):
             if parent[x] != x:
                 parent[x] = find_parent(parent[x])
             return parent[x]
         
         def union_parent(A, B):
             A = find_parent(A)
             B = find_parent(B)
         
             if A < B:
                 parent[B] = A
             else:
                 parent[A] = B
         
         N, M = map(int, input().split())
         parent = [i for i in range(N + 1)]
         
         edges = []
         result = []
         
         for _ in range(M):
             A, B, C = map(int, input().split())
             edges.append((C, A, B))
         
         edges.sort()
         
         for edge in edges:
             cost, A, B = edge
         
             if find_parent(A) != find_parent(B):
                 union_parent(A, B)
                 # 합집합 연산을 해줬으니 간선가중치를 리스트에 보관
                 result.append(cost)
         
         # 정렬 후 가중치를 차례차례 추가한것이므로, 마지막 가중치가 가장 크기때문에 이를 제외한 나머지의 합이 최소임
         print(sum(result[:-1]))

 

• 결과