백준 No.6497 전력난 - JAVA

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하고리 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시. 지나야 한다면 위험하다. 그래서 도시에 있는 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오

 

 

주의할 점

- 문제에 주어진 입력과 출력은 맞았는데 제출하면 런타입에러랑 25퍼에서 계속 틀렸는데 N이랑 M이 0이 주어지면 반복문을 끝내는 식으로 해야하고, graph를 초기화를 해줘야 했었다.

 

풀이

문제는 결국 도로에 불을 전부 켰을 경우 그니까 모든 그래프가 주어진 방식대로 연결된 상태에서 최소 신장트리를 구해서 해당 기존 값에서 최소신장트리를 구한 값으로 뺐을 때 값이 어떤 값이 나오는지 확인하면 답이다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {


    static ArrayList<Edge> graph = new ArrayList<>();
    static int parent[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;



       while(true){
           st = new StringTokenizer(br.readLine());

           int N = Integer.parseInt(st.nextToken());
           int M = Integer.parseInt(st.nextToken());

           if(N == 0 && M == 0) break;

           
           graph = new ArrayList<>();
           int total = 0;
           int sum = 0;
           parent = new int[N+1];


           for (int i = 0; i <= N  ; i++) {
               parent[i] = i;
           }

           for (int i = 0; i < M; i++) {
               st = new StringTokenizer(br.readLine());

               int start = Integer.parseInt(st.nextToken());
               int end = Integer.parseInt(st.nextToken());
               int cost = Integer.parseInt(st.nextToken());
               sum += cost;
               graph.add(new Edge(start,end,cost));
           }


           Collections.sort(graph, new Comparator<Edge>() {
               @Override
               public int compare(Edge o1, Edge o2) {
                   return o1.cost - o2.cost;
               }
           });

           for(Edge edge : graph){
               if(find(edge.start) != find(edge.end)){
                   total += edge.cost;
                   union(edge.start,edge.end);
               }
           }

           System.out.println(sum - total);

       }
    }

    static int find(int start){
            if(parent[start] == start){
                return start;
            }
            return parent[start] =  find(parent[start]);
    }

    static void union(int start,int end){
            start = find(start);
            end = find(end);

            if(start != end){
                parent[end]  =start;
        }
    }

    static class Edge{
        int start;
        int end;
        int cost;

        public Edge(int start,int end,int cost){
            this.start = start;
            this.end  =end;
            this.cost = cost;
        }
    }
}