20190309 1922번 : 네트워크 연결

네트워크 연결

링크

풀이

• 크루스칼 알고리즘을 이용한다.
• 크루스칼 알고리즘은 union-find 자료구조를 인지하고 있으면 쉽게 해결가능하다.
• union-find 링크
• 최소간선 비용을 구해야하기 때문에 비용에 대한 오름차순을 선행한다.
• 반복을 수행하면서 차근차근 간선에 관한 데이터를 추출하고 로직을 수행한다.
• 오랜만에 풀어보는 MST 문제인데도 불구하고 원솔브로 풀어서 스스로도 놀랐다.
• 크루스칼 알고리즘이 아닌 프림 알고리즘으로 해결 가능하다.
• 프림 알고리즘은 현재 선택한 정점을 기준 갈 수 있는 타 정점들의 비용값을 초기화
• 그 비용 값중에서 가장 낮은 값을 선택하고 그 정점을 방문
• 현재 내가 방문한 정점들에서 갈 수 있는 정점들의 비용을 다시 초기화
• 위의 로직을 반복

크루스칼 알고리즘

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
 
    static int[]parent = null;
    static int[]size = null;
    
    
    public static void main(String[] args) throws IOException {
 
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
 
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        parent = new int[n + 1];
        size = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        
        /** 간선에 대한 정보 **/
        ArrayList<Edge> list = new ArrayList<Edge>();
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            
            list.add(new Edge(a, b, cost));
        }
        
        /** 비용 오름차순 정렬  **/
        Collections.sort(list);
        int result = process(list);
        
        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }    
    
    private static int process(ArrayList<Edge> list) {
        
        int sumMinCost = 0;
        
        /** 비용이 오름차순으로 정렬된 간선 획득  **/
        for(int i = 0; i < list.size(); i++) {
            Edge edge = list.get(i);
            
            int nodeA = edge.s;
            int nodeB = edge.e;
            int cost = edge.cost;
            
            int parentOnNodeA = find(nodeA);
            int parentOnNodeB = find(nodeB);
            
            /** 사이클 형성 => 패스 **/
            if(parentOnNodeA == parentOnNodeB) {
                continue;
            }
            
            /** 사이클 미형성 => 합치기 **/
            union(parentOnNodeA, parentOnNodeB);
            sumMinCost += cost;
        }// for
        
        return sumMinCost;
    }
    
    /** 해당 노드의 부모노드를 찾는다. **/
    private static int find(int node) {
        
        if(parent[node] == node) {
            return node;
        }
        
        return parent[node] = find(parent[node]);
    }
    
    /** 주어진 두 개의 노드를 합친다. **/
    private static void union(int a, int b) {
        if(size[a] < size[b]) {
            parent[a] = b;
            size[b] += size[a];
        } else {
            parent[b] = a;
            size[a] += size[b];
        }
    }
}
 
class Edge implements Comparable<Edge>{
 
    public int s;
    public int e;
    public int cost;
    
    public Edge(int s, int e, int cost) {
        this.s = s;
        this.e = e;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Edge e) {
        /** cost 오름차순 **/
        return cost - e.cost;
    }
}

프림 알고리즘

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
 
    static int[]visited = null;
    static int[]distance = null;
    static int n = 0;
    static int m = 0;
    
    public static void main(String[] args) throws IOException {
 
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
 
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
 
        /** 방문배열 **/
        visited = new int[n + 1];
        Arrays.fill(visited, 0);
 
        /** 최단비용거리 **/
        distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        ArrayList<ArrayList<Edge>> list = new ArrayList<ArrayList<Edge>>();
        for(int i = 0; i <= n; i++) {
            /** i 정점에 대한 간선들 초기화 :: 이중 어레이이스트 **/
            list.add(new ArrayList<Edge>());
        }
        
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            
            /** a 와 b 가 cost 로 연결된 상태  **/
            list.get(a).add(new Edge(b, cost));
            list.get(b).add(new Edge(a, cost));
        }
        
        int value = process(list);
        
        bw.write(value + "\n");
        bw.flush();
        bw.close();
        br.close();
    }    
    
    private static int process(ArrayList<ArrayList<Edge>> list) {
        
        int minSumCost = 0;
        int edgeCount = 0;
        
        /** 1번 정점을 시작으로 잡는다. **/
        int vertex = 1;
        visited[vertex] = 1;
        
        /** 1번 정점을 기점으로 갈 수 있는 간선의 비용을 초기화 **/
        for(int eIndex = 0; eIndex < list.get(vertex).size(); eIndex++) {
            Edge edge = list.get(vertex).get(eIndex);
            distance[edge.e] = edge.cost;
        }
        
        /** MST :: 간선의 개수는 정점 개수 - 1  **/
        while(edgeCount != n - 1) {
            
            for(int eIndex = 0; eIndex < list.get(vertex).size(); eIndex++) {
                Edge edge = list.get(vertex).get(eIndex);
                
                /** 미방문  **/
                if(visited[edge.e] == 1) {
                    continue;
                }
                
                /** edge.e 로 가는 비용의 값 **/
                if(distance[edge.e] < edge.cost) {
                    continue;
                }
                
                /** 현재 내가 탐색한 정점에서 갈 수 있는 비용 수정 **/
                distance[edge.e] = edge.cost;
            }
            
            int tempVertex = 0;
            int min = Integer.MAX_VALUE;
            
            /** 미방문 + 가장 낮은 비용의 거리로 vertex 초기화 **/
            for(int start = 1; start < distance.length; start++) {
                if(visited[start] == 1) {
                    continue;
                }
                
                if(min > distance[start]) {
                    min = distance[start];
                    tempVertex = start;
                }
            }
            
            /** vertex 와 tempVertex 를 잇는 비용 값 누적 **/
            minSumCost += distance[tempVertex];
            
            /** tempVertex 방문 **/
            visited[tempVertex] = 1;
            
            /** vertex 초기화 **/
            vertex = tempVertex;
            
            /** 정점과 정점을 이어주는 간선 하나 추가 **/
            edgeCount += 1;
        }
        
        return minSumCost;
    }
}
 
class Edge{
 
    public int e;
    public int cost;
    
    public Edge(int e, int cost) {
        this.e = e;
        this.cost = cost;
    }
}